计算区域中有t 个点的 区域有多少个+计算几何 + 叉乘+sort+ 二分 + map poj 2398 Toy Storage

题目来源：http://poj.org/problem?id=2398

分析： 计算区域中有t 个点的 区域有多少个。

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include<map>
using namespace std;
typedef long long ll;
const int N =6000;
const double PI = 3.1415927;

struct Point{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){} // 构造函数，方便代码编写
    Point(const Point & p):x(p.x),y(p.y){}
    Point operator +(Point p){
        return Point(x+p.x,y+p.y);
    }
    Point operator-(Point p){
        return Point(x-p.x,y-p.y);
    }
    Point operator*(double d){
        return Point(x*d,y*d);
    }
    int operator*(Point p){  // 内积 点乘
        return x*p.x+ y*p.y;
    }
    int operator^(Point p){//  外积 叉乘
        return x*p.y-y*p.x;
    }
    friend ostream& operator<<(ostream& os,const Point& p ){
        os<<p.x<<" "<<p.y<<endl;
        return os;
    }
    friend istream& operator>>(istream& is, Point& p) {// Point 不能是常量，是变量
        is>>p.x>>p.y;
        return is;
    }
};
Point up[N];
Point low[N];
int num[N];
bool operator <(Point p1, Point p2)
{
     return p1.x<p2.x;

}
int n;
map<int ,int >mp;
map<int ,int >::iterator it;
void bin_search(Point p)   // 二分法，寻找点所在的区域，用叉乘，注意结束条件是 left+1== right
{
    int left=0,mid;
    int right = n+1;
    while(left<=right)
    {
        mid=(left+right) /2;
        int t=(up[mid]-low[mid])^(p-low[mid]);
        if( t >0  )
            right=mid;
        else if( t <0 )
            left=mid;
        if(left+1 == right )
        {
            num[left]++;
             break;
        }
    }
}
int main() {
    int m;
    int a,b;
    Point p;
    while(cin>>n && n)
    {
        cin>>m;
        cin>>up[0]>>low[n+1];
        low[0].x=up[0].x;
        up[n+1].x=low[n+1].x;
        for(int i=0;i<=n+1;i++)
        {
            up[i].y=up[0].y;
            low[i].y=low[n+1].y;
            num[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>a>>b;
            up[i].x=a;
            low[i].x=b;
        }
        sort(up+1,up+n+1);
        sort(low+1,low+n+1);
        mp.clear();
        for(int i=1;i<=m;i++)
        {
            cin>>p;
            bin_search(p);
        }
        for(int i=0;i<=n;i++)
            mp[num[i] ] ++;
        printf("Box
");
        for(it=mp.begin(); it != mp.end(); it++)
        {
            if(it->first > 0)
                printf("%d: %d
",it->first,it->second);
        }
    }
    return 0;
}