三角形和线段题解

~~某集训原题（逃~~

直接枚举5个点check。复杂度 $O(n^5)$ ，期望得分20分

固定三角形，线段两个端点要么都在里面，要么都在外面，要么一里一外。

都在里面一定合法，一里一外一定不合法，只要计算都在外面的合法对数。

可以发现如果线段两个端点都在三角形外面且不合法的话，一定会穿过三角形的两条边 (没有三点共线）。设两个端点为 X, Y，夹的那个三角形顶点为 O。我们在 O 那里计算，把所有 O 出发的射线按极角排序，在 OX 到 OY 之间，∆OXY 之外的每两个点都会产生-1的贡献。

现在问题变成了求给出的点集中三个点形成的三角形内点数。

可以拆成 3 个以原点为顶点的有向三角形内点数之和。把原点取成某个顶点，这样能保证原点和任意点的连线上没有别的点。还需要特判某个顶点在另两个点和原点形成的三角形内的情况。

总复杂度 $O(n^2\ log\ n + n^3)$ 。

Code:

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=305;
struct P{
    int x,y;
    P(){}
    P(int _x,int _y){
        x=_x; y=_y;
    }
    P operator +(const P &a)const{
        return P(x+a.x,y+a.y);
    }
    P operator -(const P &a)const{
        return P(x-a.x,y-a.y);
    }
    int operator *(const P &a)const{
        return x*a.y-y*a.x;
    }
}a[N];
int n;
ll ans;
int op(int x){
    return x<0?-1:1;
}
bool cmp(P x,P y){
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
void solve_outside(){
    For(i,1,n) For(j,i+1,n){
        int S1=0,S2=0;
        For(k,1,n) if (k!=i&&k!=j)
            if (op((a[k]-a[i])*(a[j]-a[i]))==-1) S1++; else S2++;
        ans+=S1*(S1-1)/2*S2+S2*(S2-1)/2*S1;
    }
}
int S[N][N];
int S1[N][N];
int S2[N][N];
int X[N],px[N],py[N];
int Qrect(int x,int y,int X,int Y){
    return S[X][Y]-S[x-1][Y]-S[X][y-1]+S[x-1][y-1];
}
void solve_inside(){
    sort(a+1,a+n+1,cmp);
    For(i,1,n) X[i]=a[i].x;
    sort(X+1,X+n+1);
    For(i,1,n) px[i]=lower_bound(X+1,X+n+1,a[i].x)-X;
    For(i,1,n) X[i]=a[i].y;
    sort(X+1,X+n+1);
    For(i,1,n) py[i]=lower_bound(X+1,X+n+1,a[i].y)-X;
    For(i,1,n) S[px[i]][py[i]]++;
    For(i,1,n) For(j,1,n) S[i][j]+=S[i][j-1];
    For(i,1,n) For(j,1,n) S[i][j]+=S[i-1][j];
    For(i,1,n) For(j,i+1,n){
        int mnx=min(a[i].x,a[j].x),mxx=max(a[i].x,a[j].x);
        int mny=min(a[i].y,a[j].y),mxy=max(a[i].y,a[j].y);
        For(k,1,n) if (k!=i&&k!=j)
            if (mnx<=a[k].x&&a[k].x<=mxx)
                if (mny<=a[k].y&&a[k].y<=mxy)
                    if ((a[k]-a[i])*(a[j]-a[i])>0) ++S1[i][j];
                    else ++S2[i][j];
    }
    For(i,1,n) For(j,i+1,n) For(k,j+1,n){
        int mnx=min(min(a[i].x,a[j].x),a[k].x);
        int mxx=max(max(a[i].x,a[j].x),a[k].x);
        int mny=min(min(a[i].y,a[j].y),a[k].y);
        int mxy=max(max(a[i].y,a[j].y),a[k].y);

        int mnxx=min(min(px[i],px[j]),px[k]);
        int mxxx=max(max(px[i],px[j]),px[k]);
        int mnyy=min(min(py[i],py[j]),py[k]);
        int mxyy=max(max(py[i],py[j]),py[k]);

        int SS=Qrect(mnxx,mnyy,mxxx,mxyy)-3;
        SS-=((a[k]-a[i])*(a[j]-a[i])>0?S2[i][j]:S1[i][j]);
        SS-=((a[j]-a[i])*(a[k]-a[i])>0?S2[i][k]:S1[i][k]);
        SS-=((a[i]-a[j])*(a[k]-a[j])>0?S2[j][k]:S1[j][k]);
        if (a[i].y<a[j].y&&a[j].y<a[k].y&&a[i].x<a[j].x&&a[j].x<a[k].x)
            if ((a[k]-a[i])*(a[j]-a[i])<0)
                SS-=Qrect(px[j]+1,py[i],px[k],py[j]-1);
            else SS-=Qrect(px[i],py[j]+1,px[j]-1,py[k]);

        if (a[i].y>a[j].y&&a[j].y>a[k].y&&a[i].x<a[j].x&&a[j].x<a[k].x)
            if ((a[k]-a[i])*(a[j]-a[i])<0)
                SS-=Qrect(px[i],py[k],px[j]-1,py[j]-1);
            else SS-=Qrect(px[j]+1,py[j]+1,px[k],py[i]);
        ans+=SS*(SS-1)/2;
    }
}
int main(){
    srand(time(NULL));
    scanf("%d",&n);
    For(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
    solve_outside();
    solve_inside();
    printf("%lld",ans);
}

三角形和线段 题解

三角形和线段题解