跨产品的利用率推断点线段向左或向右,然后你可以2分钟
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5005;
int n, m, x1, y1, x2, y2;
struct Point {
int x, y;
Point() {}
Point(int x, int y) {
this->x = x;
this->y = y;
}
};
typedef Point Vector;
Vector operator - (Vector A, Vector B) {
return Vector(A.x - B.x, A.y - B.y);
}
struct Seg {
Point a, b;
Seg() {}
Seg(Point a, Point b) {
this->a = a;
this->b = b;
}
} seg[N];
int ans[N];
int Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
void gao(Point p) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (Cross(seg[mid].a - p, seg[mid].b - p) < 0) r = mid;
else l = mid + 1;
}
ans[l]++;
}
int main() {
while (~scanf("%d", &n) && n) {
memset(ans, 0, sizeof(ans));
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
int x, y;
for (int i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
seg[i] = Seg(Point(x, y1), Point(y, y2));
}
for (int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
gao(Point(x, y));
}
for (int i = 0; i <= n; i++)
printf("%d: %d\n", i, ans[i]);
printf("\n");
}
return 0;
}
转载于:https://www.cnblogs.com/lcchuguo/p/4590737.html