本文共 1553 字，大约阅读时间需要 5 分钟。
给定一个矩形，n个线段将矩形分成n+1个区间，m个点，问这些点的分布。
思路就是叉积加二分，利用叉积判断点与直线的距离，二分搜索区间。
最近整理了STL的一些模板，发现真是好用啊orz，为啥以前没发现呢，可能是比较懒吧-.-
#include #include #include #include #include #include #include #include #include #include #include #include #define mem(arr,num) memset(arr,0,sizeof(arr))#define _for(i, a, b) for(int i = a; i <= b; i++)#define __for(i, a, b) for(int i = a; i >=b; i--)using namespace std;typedef long long ll;const ll INF = 0x3f3f3f3f;const int N = 5000+5;struct P{ int x,y; P() {} P(int a, int b) { x = a, y = b; } P operator- (P b) { return P(x-b.x,y-b.y); }} L,R,p[N];pair pr;vector > line;double cross(P a, P b) { return a.x * b.y - a.y * b.x;}double judge(P c, P a, P b){ return cross(c - a,b - a);}int res[N];int main(){ int n, m; while(cin >> n, n) { mem(res,0); line.clear(); cin >> m >> L.x >> L.y >> R.x >> R.y; pr.second = L; pr.first.x = L.x, pr.first.y = R.y; line.push_back(pr); _for(i, 1, n) { int a, b; P p; cin >> a >> b; p.x = a, p.y = L.y; pr.second = p; p.x = b, p.y = R.y; pr.first = p; line.push_back(pr); } pr.second.x = R.x, pr.second.y = L.y; pr.first = R; line.push_back(pr); _for(i, 1, m) cin >> p[i].x >> p[i].y; _for(i, 1, m) { int l = 0, r = line.size()-1,mid; while(r - l != 1){ mid = (l+r)/2; P _x = line[mid].first,_y = line[mid].second; if(judge(p[i], _x, _y)<0) r = mid; else l = mid; } res[l] ++; } _for(i, 0, n) cout << i <<": "<< res[i] <
转载于:https://www.cnblogs.com/GHzz/p/8783291.html