2019牛客暑期多校第八场 Flower Dance

题意

给一些点，找4个点，要求1个点在剩余三个点围成的三角形的内部，问方案数

题解

写得我有种不想碰几何的冲动。。。。
太迷了，精度迷，同一种意思的不同表达迷，明明那么简洁的思路，为什么写出来这么多特殊情况 😐
哭了

枚举每一个点当做三角形内部的点，看有多少个三角形能包住他

1号能和（4,5）（3,5）（2,5）组成
明显，1号之外的2个点的夹角不能大于180（逆时针转过去）
所以，我们要求出来每个点逆时针转180度以内有多少个点
另 $f\left[i\right]$f[i] 表示上述函数
1的180度内的点有2、3、4
答案就是 $f\left[2\right]+f\left[3\right]+f\left[4\right]$f[2]+f[3]+f[4] 吗？
不是，要删去一部分
观察发现，另外2个点必须分布在1的两侧，所以
$f\left[4\right]$f[4]全是答案
$f\left[3\right]$f[3]要少算4
$f\left[2\right]$f[2]要少算4、3
显然，少算的个数是一个形如 $0,1,\mathrm{2...}n-1$0,1,2...n−1 的等差数列，所以这部分知道 $f\left[\right]$f[ ] 后 $O\left(1\right)$O(1)就可以得到
完了吗？
没有 😦
发现和1共线且在对侧的点不能算，但会被计算
所以要求出1对面共线的点的个数，乘以 $f\left[1\right]$f[1] 就是要减的数量。。。。。。。。。吗？
不是
因为 $f\left[\right]$f[ ]包含了和1共线且同侧的点，是不需要减的，因为之前算个数加的时候就没有加（本身不合法）
综上，我们要计算
逆时针0度的点的个数，逆时针大于0小于180度的点的个数，逆时针180度的点的个数。。。。

┏┛墓┗┓…(((m-__-)m

代码

#include<bits/stdc++.h>
#define N 2010
#define INF 0x3f3f3f3f
#define eps 1e-6
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y) 
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
int dcmp(double x){if (fabs(x)<eps)return 0;else return x<0?-1:1;}
struct Point
{
    LL x,y;
    bool operator < (const Point &a)const
    {return (x-a.x)<0 || ((x-a.x)==0 && (y-a.y)<0);}
    Point(LL x=0,LL y=0):x(x),y(y){ }
}a[N],c[N];
typedef Point Vector;
  
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,LL b){return Vector(a.x*b,a.y*b);}
bool operator == (Vector a,Vector b){return (a.x-b.x)==0 && (a.y-b.y)==0;}
inline LL Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
inline LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}  //点积
inline double Length(Vector a){return sqrt(Dot(a,a));}
inline double Angle(Vector a,Vector b){return acos(min(1.0,max(-1.0,Dot(a,b)/Length(a)/Length(b))));}
bool cmp(Point a,Point b){
    if(a.y<0 && b.y>=0 || a.y>=0 && b.y<0) return a.y>=0;
    if(a.y*b.y==0)
    {
        if(a.y==0 && b.y==0) return a.x>b.x;
        return Cross(a,b)>0;
    }
    return Cross(a,b)>0;
}
 
LL ans=0;
int cnt;
int v[N<<1],d[N<<1],p[N],w[N];
 
//从a逆时针旋转到b转过的角度，范围[0,360)
double GetAngle(Vector a,Vector b)
{
    double x=Angle(a,b),y=Cross(a,b);
    if (dcmp(y)<0)x=pi*2-x;
    return x;
}
 
void slove(){
    sort(c,c+cnt,cmp);
 
    if (dcmp(GetAngle(c[0],c[cnt-1])-pi)<=0) return;
    for(int i=0;i<cnt-1;i++)
        if (dcmp(GetAngle(c[i],c[i+1])-pi)>=0) return;
 
 
    for(int i=0;i<cnt;i++) c[i+cnt]=c[i];
  
    int k=0,ka=0,kb=0,m=cnt<<1;
    
    for(int i=0;i<cnt;i++){
        k=max(k,i);ka=max(ka,i);kb=max(kb,i);
 
        while(k<m&&(dcmp(GetAngle(c[i],c[k+1]))==0||Cross(c[i],c[k+1])>0)) k++;
        v[i]=v[i+cnt]=k-i;
 
        while(ka<m&&Cross(c[i],c[ka+1])>=0) ka++;
        w[i]=ka-k;
 
        while(kb<m&&Cross(c[i],c[kb+1])==0&&Dot(c[i],c[kb+1])>0) kb++;
        p[i]=kb-i;
 
    }
  
    d[0]=v[0]; for(int i=1;i<m;i++) d[i]=d[i-1]+v[i];
    for(int i=0;i<cnt;i++){
 
        int sz=v[i]-p[i];
 
        int t=(d[i+v[i]]-d[i+p[i]])-sz*(sz-1)/2-sz*w[i];
 
        ans+=t;
 
    }
}
  
int main(int argc, char const *argv[])
{
 
    int n;
    sc(n);
    for(int i=0;i<n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
    for(int i=0;i<n;i++){
        cnt=0;
        for(int j=0;j<n;j++) if (i^j) c[cnt++]=a[j]-a[i];
        slove();
    }
    cout<<ans/3;
    return 0;
}