【题解】POJ2318Toys-计算几何

POJ2318

大致题意

给定一个矩阵的四个顶点坐标，和矩阵内的条直线和个点，求每个被直线分成的区域内各包含多少点

思路

对于条边，我们通过二分查找到当前点右边的第一条边（因为点不可能存在于边上）就是该点所存在的区域。我们可以通过这个点和边的有向面积的正负判断点在线段的哪个方位。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double,double> PDD;
#define fi first
#define se second
#define mp make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(0)
const int N = 5000 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;

int n,m;
PLL a[N],b[N];
int ans[N];

LL cross(LL x1,LL x2,LL y1,LL y2){
    return x1 * y2 - x2 * y1;
}


LL area(PLL xx,PLL yy,PLL zz){
    return cross(xx.fi - yy.fi,xx.se - yy.se,zz.fi - yy.fi,zz.se - yy.se);
}


int find(int x,int y){
    int l = 0,r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (area(a[mid],b[mid],mp(x,y)) > 0) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main(){
    bool f = 1;
    while (cin >> n,n){
        LL x1,y1,x2,y2;
        cin >> m >> x1 >> y1 >> x2 >> y2;
        for (int i = 0;i <  n;++i){
            int u,k;cin >> u >> k;
            a[i] = mp(u,y1),b[i] = mp(k,y2);
        }
        a[n] = mp(x2,y1),b[n] = mp(x2,y2);
        memset(ans,0,sizeof ans);
        while (m--){
            int u,k;cin >> u >> k;
            ans[find(u,k)]++;
        }
        if (f)    f = 0;
        else puts("");

        for (int i = 0;i <= n;++i){
            printf("%d: %d\n",i,ans[i]);
        }
    }
    return 0;
}