学步园

计算几何终于开搞，热烈庆祝！！撒花~*★,°*:.☆\(￣▽￣)/$:*.°★*

抄了梁平君基础板子，相信他不会介意的~

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
using namespace std;
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8

const int maxn = 5010;

///返还1表示大于0，返回-1表示小于0，返回0表示等于0
int sig(double x) { return ((x>eps)-(x<-eps));}

struct point
{
        double x, y;
        point(double _x = 0, double _y = 0): x(_x), y(_y) {}
        point operator + (const point &p) { return point(x+p.x, y+p.y);}
        point operator - (const point &p) { return point(x-p.x, y-p.y);}
        double operator * (const point &p) { return (x*p.x + y*p.y);}
        double operator ^ (const point &p) { return (x*p.y - y*p.x);}
        void in() { scanf("%lf%lf", &x, &y);}
        void out() { printf("%lf %lf\n", x, y);}
        void cha(double _x, double _y) { x = _x; y = _y;}
};

struct segment
{
        point st, en;
};

segment cp[maxn];
int grid[maxn];

int binasearch(point &t, int l, int r)
{
        if(l >= r) return l-1;
        int m = (l + r) >> 1;
        ///大于0在第m条隔断的前面，小于0在后面
        double dt = (t-cp[m].st) ^ (cp[m].en-cp[m].st);
        if(sig(dt) < 0) binasearch(t, m+1, r);
        else binasearch(t, l, m);
}

int main()
{
        #ifdef BellWind
        freopen("A.in", "r", stdin);
        #endif // BellWind

        int n, m;
        while(~scanf("%d%d", &n, &m) && n)
        {
                (cp[0].st).in();
                (cp[n+1].en).in();
                (cp[0].en).cha((cp[0].st).x, (cp[n+1].en).y);
                (cp[n+1].st).cha((cp[n+1].en).x, (cp[0].st).y);
                double xu, xl;
                for(int i = 1; i <= n; i++)
                {
                        scanf("%lf%lf", &xu, &xl);
                        (cp[i].st).cha(xu, (cp[0].st).y);
                        (cp[i].en).cha(xl, (cp[n+1].en).y);
                }
                point toy;
                memset(grid, 0, sizeof(grid));
                for(int i = 0; i < m; i++)
                {
                        toy.in();
//                        toy.out();
                        int k = binasearch(toy, 0, n+1);
                        grid[k]++;
                }
                for(int i = 0; i <= n; i++)
                {
                        printf("%d: %d\n", i, grid[i]);
                }
                printf("\n");
        }

        return 0;
}