计算几何 专题

/**************************************************************
    Problem:poj 2318
    User: youmi
    Language: C++
    Result: Accepted
    Time:922MS
    Memory:852K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep0(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep_1(i,n) for(int i=n;i>=1;i--)
#define rep_0(i,n) for(int i=n-1;i>=0;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-8
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl

using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
int n,m;

const int maxn=5000+10;
int sgn(double x)
{
    if(fabs(x)<eps)
        return 0;
    if(x<0)
        return -1;
    else
        return 1;
}
struct Point
{
    double x,y;
    Point(){};
    Point(double _x,double _y)
    {
        x=_x,y=_y;
    }
    Point operator- (const Point &_b)const
    {
        return Point(x-_b.x,y-_b.y);
    }
    double operator*(const Point &_b)const
    {
        return x*_b.x+y*_b.y;
    }
    double operator^(const Point &_b)const
    {
        return x*_b.y-y*_b.x;
    }
    void transXY(double _B)
    {
        double tx=x,ty=y;
        x=tx*cos(_B)-ty*sin(_B);
        y=tx*sin(_B)+ty*cos(_B);
    }
};
double cross(struct Point _s,struct Point _e1,struct Point _e2)
{
    Point s,e;
    s=Point(_e1.x-_s.x,_e1.y-_s.y);
    e=Point(_e2.x-_s.x,_e2.y-_s.y);
    return s^e;
}
Point p[maxn],q[maxn];
int cnt[maxn];
void sovle(struct Point cur)
{
    for(int i=1;i<=n;i++)
    {
        if(sgn(cross(p[i],q[i],cur)*cross(p[i-1],q[i-1],cur))==-1)
        {
            cnt[i-1]++;
            return;
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int kase=0;
    while(~sc(n)&&n)
    {
        if(kase++)
            cout<<endl;
        sc(m);
        int x1,y1,x2,y2;
        sc2(x1,y1);
        p[0].x=x1,p[0].y=0;
        q[0].x=x1,q[0].y=y1;
        sc2(x2,y2);
        p[n+1]=Point(x2,y2);
        q[n+1]=Point(x2,y1);
        rep1(i,n)
        {
            sc2(x1,x2);
            p[i]=Point(x2,y2);
            q[i]=Point(x1,y1);
        }
        ++n;
        /**< for(int i=0;i<=n;i++)
        {
            printf("%.0f %.0f\t%.0f %.0f\n",p[i].x,p[i].y,q[i].x,q[i].y);
        } */
        zeros(cnt);
        Point cur;
        rep1(i,m)
        {
            scanf("%lf%lf",&cur.x,&cur.y);
            sovle(cur);
        }
        for(int i=0;i<n;i++)
            printf("%d: %d\n",i,cnt[i]);
    }
    return 0;
}