本文共 1851 字，大约阅读时间需要 6 分钟。
题目来源：http://poj.org/problem?id=2398
分析： 计算区域中有t 个点的 区域有多少个。
#include #include #include #include #include #include #include #include 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< <<" "< < >(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 mp;map ::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\n"); for(it=mp.begin(); it != mp.end(); it++) { if(it->first > 0) printf("%d: %d\n",it->first,it->second); } } return 0;}
转载于:https://www.cnblogs.com/zn505119020/p/3623818.html