POJ2318 TOYS（计算几何）

February 14, 2016

题目链接

题意：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;
}