CodeForces - 1019D（BZOJ3707圈地）：Large Triangle （几何，找面积为S的三角形）

题意：给定平面上N个点，问是否存在三角形，其面积为S。

思路：选择Y轴，枚举这个Y轴，面积大小只与|y-Y|有关，然后二分，具体的可以先去做BZOJ3707。

具体的：

1，先对点排序，X坐标为第一关键字，Y坐标为第二关键字，从小到大排序。

2，得到C(N,2)条直线，按照它们的斜率为关键字（叉积排序比较准确），从小到大排序。

3，二分答案，对当前直线，我们只处理线段左边（相对来说）的点，左边的点距离当前“Y轴”具有单调性。

而得到当前直线的两个点，相对于下一条直线，其相对位置会发生改变。

简单证明：（瞎证，笔画以下就知道了）

第一个直线L斜率最小，那么它左边的点，到它的相对位置大小，就是第一次排序后的大小：否则L不是斜率最小，易证。

由上一条直线，到下一条直线，对于新的“Y轴”，相对位置改变的只有上一条直线的两点：否则斜率大小有误，易证。

#include <bits/stdc++.h>

#define rep(i,j,k) for(int i=j;i<=k;i++)

using namespace std;

typedef long long ll;

const int maxn=;

struct Point {

    int x,y;

    bool operator<(const Point& B) const {

        return x^B.x?x<B.x:y<B.y;

    }

}P[maxn];

typedef Point Vector;

Vector operator - (Vector u, Vector v) { return (Vector){u.x-v.x,u.y-v.y}; }

Vector operator + (Vector u, Vector v) { return (Vector){u.x+v.x,u.y+v.y}; }

ll Cross(Vector u,Vector v) { return 1ll * u.x * v.y - 1ll * u.y * v.x; }

struct Segment {

    int u, v;

    Vector p;

    bool operator<(const Segment& B) const {

        return Cross(p, B.p)>;

    }

}A[maxn*maxn];

int N,M,pos[maxn]; ll S;

int main() {

    cin>>N>>S; S<<=1LL;

    rep(i,,N) cin>>P[i].x>>P[i].y;

    sort(P+,P+N+);

    rep(i,,N) pos[i]=i;

    rep(i,,N) rep(j,i+,N) A[++M]=(Segment){i,j,P[i]-P[j]};

    sort(A+,A+M+);

    rep(i,,M) {

        int &a=pos[A[i].u],&b=pos[A[i].v];

        Vector p=P[b]-P[a];

        int l=,r=a-;

        while(l<r){

            int mid=(l+r+)>>;

            if(abs(Cross(p,P[mid]-P[a]))>=S) l=mid;

            else r=mid-;

        }

        if(abs(Cross(p,P[l]-P[a]))==S){

            printf("Yes\n%d %d\n%d %d\n%d %d\n", P[a].x, P[a].y, P[b].x, P[b].y, P[l].x, P[l].y);

            return ;

        }

        swap(a,b);

        swap(P[a],P[b]);

    }

    puts("No");

    return ;

}

巴特西

CodeForces - 1019D（BZOJ3707圈地）：Large Triangle （几何，找面积为S的三角形）

最新文章

热门文章