【题目】题目链接
Kiwon's favorite video game is now holding a new year event to motivate the users! The game is about building and defending a castle, which led Kiwon to think about the following puzzle.
In a 2-dimension plane, you have a set s={(x1,y1),(x2,y2),…,(xn,yn)}s={(x1,y1),(x2,y2),…,(xn,yn)} consisting of nn distinct points. In the set ss, no three distinct points lie on a single line. For a point p∈sp∈s, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with 44 vertices) that strictly encloses the point pp (i.e. the point pp is strictly inside a quadrilateral).
Kiwon is interested in the number of 44-point subsets of ss that can be used to build a castle protecting pp. Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.
Let f(p)f(p) be the number of 44-point subsets that can enclose the point pp. Please compute the sum of f(p)f(p) for all points p∈sp∈s.
The first line contains a single integer nn (5≤n≤25005≤n≤2500).
In the next nn lines, two integers xixi and yiyi (−109≤xi,yi≤109−109≤xi,yi≤109) denoting the position of points are given.
It is guaranteed that all points are distinct, and there are no three collinear points.
Print the sum of f(p)f(p) for all points p∈sp∈s.
5 -1 0 1 0 -10 -1 10 -1 0 3
2
8 0 1 1 2 2 2 1 3 0 -1 -1 -2 -2 -2 -1 -3
40
10 588634631 265299215 -257682751 342279997 527377039 82412729 145077145 702473706 276067232 912883502 822614418 -514698233 280281434 -41461635 65985059 -827653144 188538640 592896147 -857422304 -529223472
213
【题意】
求对每个点x，f（x）有多少四边形能把这个点包在内；求所有点f（x）的和。
【题解】
发现找几个四边形是很难的，反着想：全部的不包括当前点的四边形为 n*C（n-1，4）。
取当前点P0为原点，每个点与它连线，枚举除它外的另一个点P1，发现与P0/P1选在同一侧的3个点的四边形肯定是不满足的，把这些四边形去掉
找与当前点同一侧的时候，可以利用atan2（y,x）函数，求（x,y）点与原点连线对x轴正方向的角度，取值为[-π，π].相差π内的在同一侧。（注意将负的值加上2π）
可以把点从小到大排序，然后二分查找（注意循环枚举每一个点）
-精度问题
π要用 long double const pai=acos(-1.0L);
随手开 long double
ac代码
1 //这个就是如果定下了四边形中的一个点那么，如果剩下三个点都在一边，那么是不可以的情况 2 #include<algorithm> 3 #include<cstdio> 4 #include<vector> 5 #include<cmath> 6 #define maxn 2505 7 using namespace std; 8 typedef long long ll; 9 const long double pai = acos(-1.0L);//注意1.0后面有个L，这个影响精度的很重要 10 int n; 11 long long int x[maxn], y[maxn]; 12 vector<long double> v; 13 signed main() { 14 scanf("%d",&n); 15 for(int i = 0; i < n; i++) scanf("%lld%lld", &x[i], &y[i]); 16 17 ll ans = 1ll * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 24;//C_n^5，所有情况数 18 for(int i = 0; i < n; i++) { 19 v.clear(); 20 for(int j = 0; j < n; j++) if(i != j) v.push_back(atan2(x[j] - x[i], y[j] - y[i]));//放进每个点的角度 21 sort(v.begin(), v.end());//排个序 22 register int now = 0;//用now线性扫描，可以降低复杂度的 23 ll cnt; 24 for(int j = 0; j < n - 1; j++) { 25 while(now < j + n - 1) {//因为平面是环形的，所以用延长一倍的技巧 26 long double tmp = v[now % (n - 1)] - v[j];//这才是这个点相对点j的实际角度 27 if(tmp < 0) tmp += (long double)2 * pai;//多转一圈好判定 28 if(tmp < pai) now++; 29 else break;//大于π了明显不合法了 30 } 31 cnt = (now - j - 1);//这里的边界手枚一下就很好理解的 32 ans -= cnt * (cnt - 1) * (cnt - 2) / 6;//cnt一定要开Long long！！这很重要 c n 3 33 } 34 } 35 printf("%lld ", ans); 36 return 0; 37 }
没有ac的代码，然而我看不出是哪里的精度问题
1 #include<bits/stdc++.h> 2 using namespace std; 3 int const maxn=2550; 4 long double const pai=acos(-1.0L);//这个地方π一定要这样求！否则会出精度问题！ 5 typedef long long ll; 6 int n; 7 ll ans; 8 ll x[maxn],y[maxn]; 9 long double ang[maxn]; 10 ll com(ll nn,ll mm){ 11 if(mm>nn)return 0; 12 ll ans2=1ll; 13 for(ll i=nn-mm+1;i<=nn;i++)ans2*=i; 14 for(ll i=2;i<=mm;i++)ans2/=i; 15 return ans2; 16 } 17 ll binary(int index){ 18 ll l=index+1,r=index+n-2,ans1=0,mid; 19 while(l<=r){ 20 mid=(l+r)>>1; 21 if(ang[mid]-ang[index]<=pai)l=mid+1,ans1=mid; 22 else r=mid-1; 23 } 24 if(ans1&&ans1-index>2)return ans1-index; 25 else return 0; 26 } 27 int main(){ 28 scanf("%d",&n); 29 for(int i=1;i<=n;i++){ 30 scanf("%lld%lld",&x[i],&y[i]); 31 } 32 ans=1ll*n*(n-1)*(n-2)*(n-3)*(n-4)/24; 33 //printf("%lf %lf %lf ",atan2(-1,0),atan2(2,0),atan2(0,-3)); 34 for(int i=1;i<=n;i++){ 35 int tot=0; 36 for(int j=1;j<=n;j++)if(j!=i){ 37 ang[++tot]=atan2(y[j]-y[i],x[j]-x[i]); 38 if(ang[tot]<0.0)ang[tot]+=2*pai; 39 } 40 sort(ang+1,ang+n); 41 for(int j=1;j<n;j++)ang[j+n-1]=ang[j]+2*pai; 42 43 for(int j=1;j<n;j++){ 44 ans-=com(binary(j),3); 45 } 46 } 47 printf("%lld ",ans); 48 return 0; 49 }