UVa11592 Strange Tax Calculation

题目

UVa11592 Strange Tax Calculation

题解

恩？不相交？我会算总个数。然后？我好像会n^4枚举？好像连这个都写不来。看到平均数就被带偏了，后来一想求平均数不是和求总个数一样的吗qwq。

没有办法只好看题解。

啊好巧妙啊。虽然我也想过对于每一个点计算它的被包括次数，可是实际上做法是每句一个中心点p作为原点，然后将剩下的按极角排序，排完之后从极角最小的一个点开始枚举a，找到另一个临界点b，使得极角apb（不知道表述是否恰当，反正是那个意思qwq）刚好小于pi,这样能计算出以a为一个顶点，不包含p的三角形有多少个（这里并没有算完，只算了a作为极角较小的那一个顶点时的情况，但是根据这种方法，在后面算的时候能不重不漏的算完），由于会形成一个环所以要扩二倍来算，然后用n-1个点总共形成的三角形数目减去不包含p的就是包含p的了，然后求个和就能出解了qwq。

代码

//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1200+10;
int x[maxn],y[maxn];
const double pi=acos(-1.0);ll tempsum;int n;inline ll C3(int x){
   return 1ll*x*(x-1)*(x-2)/6;}//求C(x,3)
inline ll C2(int x){
   return 1ll*x*(x-1)/2;}//求C(x,2)double deg[maxn*2];
inline ll work(int p)
{int pcnt=0;for(int i=1;i<=n;++i) if(i!=p) deg[++pcnt]=atan2(y[i]-y[p],x[i]-x[p]);sort(deg+1,deg+n);for(int i=1;i<n-1;++i) deg[i+n-1]=deg[i]+2*pi;int pos=1;ll ret=0;for(int i=1;i<n;++i){pos=max(pos,i);while(pos+1<=i+n-2&&deg[pos+1]<deg[i]+pi) ++pos;ret+=C2(pos-i);}return tempsum-ret;
}   int kase=0;
inline void solve()
{for(int i=1;i<=n;++i) scanf("%d%d",x+i,y+i);ll ALL=C3(n),cnt=0;if(n>=4){tempsum=C3(n-1);for(int i=1;i<=n;++i) cnt+=work(i);}printf("City %d: %.2f\n",++kase,(double)cnt/ALL);
}int main()
{while(scanf("%d",&n)==1&&n) solve();return 0;
}