Description
Input
输入第一行包含一个正整数 n, 表示房子的总数。
接下来有 n 行，分别表示 每一个房子的位置。对于 i = 1, 2, .., n, 第 i 个房子的坐标用一对整数 \(x_i,y_i\) 来表示，中间用空格隔开。
Output
输出文件包含一个六位小数，表示平均有多少个房子被信号所覆盖。
Sample Input
4
0 2
4 4
0 0
2 0
Sample Output
3.500000
HINT
\(–1,000,000 ≤ x_i,y_i ≤ 1,000,000,3 ≤ n ≤ 1,500\).
任何三个房子不在同一条直线上，任何四个房子不在同一个圆上。
Solution
显然我们是要考虑第四个点何时产生贡献.如果直接讨论,是\(O(n^4)\),所以考虑四边形的形态对答案的影响.
如果是凹四边形, 只有1种情况包含第四个点;
如果是凸四边形, 只有2种情况包含第四个点(对角和>180°的顶点为第四个点时).
统计凹四边形的数量: 枚举凹四边形里的中间点,求出此时凸四边形的数量，即可求出凹四边形的数量。把其他点按以它为原点时的极角排序，枚举每个点作为四边形与中间点相邻的点，每个极角求出逆时针方向离它最远不超过\(\pi\)的极角t，然后这个极角之后到t的所有点都可作为凸四边形的其余两个点。
至此，答案就很好统计了。
#define N 1505
typedef long long ll;
struct point{
int x,y;double an;
}a[N],p[N];
int n;
double tot;
bool operator < (point a,point b){
return a.an<b.an;
}
point operator - (point a,point b){
return (point){a.x-b.x,a.y-b.y};
}
ll operator * (point a,point b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
double atan2(point a){
return atan2(a.y,a.x);
}
inline double C(int n,int m){
if(m>n) return 0.0;
double ret=1.0;
for(int i=n-m+1;i<=n;++i) ret*=(double)(i);
for(int i=1;i<=m;++i) ret/=(double)(i);
return ret;
}
inline double func(int u){
double ret=C(n-1,3);int tot=0;
for(int i=1;i<=n;++i) p[i]=a[i];
swap(p[1],p[u]);
for(int i=2;i<=n;++i) p[i].an=atan2(p[i]-p[1]);
sort(p+2,p+1+n);
for(int i=2,j=3;i<=n;++i){
while((p[i]-p[1])*(p[j]-p[1])>=0){
j=(++j>n)?2:j;++tot;
if(j==i) break;
}
ret-=C(tot,2);--tot;
}
return ret;
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;++i) tot+=func(i);
printf("%lf\n",3.0+(tot+(2.0*(C(n,4)-tot)))/C(n,3));
}
2017-05-03 22:37:49