POJ2318 TOYS(计算几何)

题目链接

题意:n+1个区域和m个点,求每个区域内点的个数。

思路:直接枚举,ans[i]表示在第i个线段左侧点的个数。用点与线段两端点构成的两个向量的差积的正负判断这个点在线段的左侧还是右侧。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int line[5005][4];
int main(){
    //freopen("a.txt", "r", stdin);
    int n, m, x1, y1, x2, y2;
    bool flag = 1;
    while(scanf("%d", &n) != 0 && n){
        if(flag) flag = 0;
        else cout << endl;
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        int ui, li;
        for(int i = 0; i < n; i++){
            scanf("%d%d", &ui, &li);
            line[i][0] = ui;
            line[i][1] = y1;
            line[i][2] = li;
            line[i][3] = y2;
        }
        int ans[5005];
        memset(ans, 0, sizeof(ans));
        int a, b;
        for(int i = 0; i < m; i++){
            scanf("%d%d", &a, &b);
            for(int j = 0; j < n; j++){
                x1 = line[j][0]-a;
                y1 = line[j][1]-b;
                x2 = line[j][2]-a;
                y2 = line[j][3]-b;
                if((x1*y2-x2*y1)<0)
                    ans[j]++;
            }
        }
        ans[n] = m;
        for(int i = 0; i <= n; i++){
            cout << i << ": ";
            if(!i) cout << ans[0] << endl;
            else cout << ans[i]-ans[i-1] <<endl;
        }
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 计算几何