LOJ#2882. 「JOISC 2014 Day4」两个人的星座（计算几何）

题面

传送门

题解

我们发现如果两个三角形相离，那么这两个三角形一定存在两条公切线

那么我们可以\(O(n^2)\)枚举其中一条公切线，然后可以暴力\(O(n^3)\)计算

怎么优化呢？我们可以枚举一个定点，然后把其它所有点按到这个定点的极角排序，那么就可以\(O(n^2)\)得出答案了

//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=3005;const double Pi=acos(-1.0);
int c[2][5],bl[N],n;ll res;
struct node{
    int x,y,c;double k;
    inline node(){}
    inline node(R int xx,R int yy):x(xx),y(yy){}
    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
    inline double K(){return atan2(y,x);}
    inline bool operator <(const node &b)const{return k<b.k;}
}st[N],p[N];
inline int calc(R int k,R int x){
    switch(x){
        case 0:return c[k][1]*c[k][2];break;
        case 1:return c[k][0]*c[k][2];break;
        case 2:return c[k][0]*c[k][1];break;
    }
}
void solve(int id){
    int top=0;
    fp(i,1,id-1)p[++top]=st[i],p[top].k=(st[i]-st[id]).K();
    fp(i,id+1,n)p[++top]=st[i],p[top].k=(st[i]-st[id]).K();
    fp(i,1,top)if(p[i].k<=0)p[i].k+=Pi;
    sort(p+1,p+1+top);
    c[0][0]=c[0][1]=c[0][2]=c[1][0]=c[1][1]=c[1][2]=0;
    fp(i,1,top)if(p[i].y<st[id].y||p[i].y==st[id].y&&p[i].x>st[id].x)
        ++c[0][p[i].c],bl[i]=0;
    else ++c[1][p[i].c],bl[i]=1;
    fp(i,1,top){
        --c[bl[i]][p[i].c],res+=1ll*calc(0,st[id].c)*calc(1,p[i].c);
        res+=1ll*calc(1,st[id].c)*calc(0,p[i].c),bl[i]^=1,++c[bl[i]][p[i].c];
    }
}
int main(){
//  freopen("testdata.in","r",stdin);
    n=read();
    fp(i,1,n)st[i].x=read(),st[i].y=read(),st[i].c=read();
    fp(i,1,n)solve(i);
    printf("%lld\n",res>>2);
    return 0;
}