题目：传送门
思路：先枚举被围的点p，以p为坐标原点，建立坐标系，并求出所有点在坐标系中的弧度角。在枚举p以外的的一个点x，与x角度相差π以内的三个点（p除外），所围出的四边形必定不包含点p。因此我们可采取总方案数 n*C(4,n-1) - 不合法的方案数，求出答案。
1 #include<bits/stdc++.h> 2 #pragma GCC optimize(2) 3 using namespace std; 4 typedef long long LL; 5 typedef pair<int,int> pii; 6 typedef pair<double,double> pdd; 7 const int N=3e3+5; 8 const int inf=0x3f3f3f3f; 9 const int mod=1e9+7; 10 const double eps=1e-9; 11 const long double pi=acos(-1.0L); 12 #define ls (i<<1) 13 #define rs (i<<1|1) 14 #define fi first 15 #define se second 16 #define pb push_back 17 #define mk make_pair 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 LL read() 20 { 21 LL x=0,t=1; 22 char ch; 23 while(!isdigit(ch=getchar())) if(ch=='-') t=-1; 24 while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } 25 return x*t; 26 } 27 long double x[N],y[N]; 28 int main() 29 { 30 int n=read(); 31 LL ans=1LL*(n-4)*(n-3)*(n-2)*(n-1)*n/24;//n*C(4,n-1); 对于每一个点找四条边围住 32 for(int i=1;i<=n;i++) scanf("%Lf%Lf",x+i,y+i); 33 for(int i=1;i<=n;i++)//枚举固定点 p（被围的点） 34 { 35 vector<long double> de; 36 for(int j=1;j<=n;j++) 37 { 38 if(i==j) continue; 39 long double t=atan2(y[j]-y[i],x[j]-x[i]); 40 de.pb(t); 41 } 42 sort(de.begin(),de.end()); 43 int now=0,m=n-1; 44 for(int j=0;j<de.size();j++)//枚举固定边 （围p的一条边） 45 { 46 for(;now<j+m;now++)//now>=j&&now<j+m 一共m条边，除去自己一共m-1条，最多取m-1 作组合数运算; 47 { 48 long double t=de[now%m]-de[j]; 49 if(t<0) t+=2*pi; 50 if(t>pi) break;//now 不合法 退出当前循环; 51 } 52 LL cnt=now-1-j;//合法的边： j+1 ~ now-1; 53 ans-=(cnt-2)*(cnt-1)*cnt/6; 54 } 55 } 56 printf("%lld ",ans); 57 return 0; 58 }