题目链接:POJ 2318 TOYS
用点积判断一个点在直线的哪一侧,由于题目给出的分割线是排序后的,那么可以直接用二分得出答案。
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const double eps = 1e-10; const int MAX_N = 5000 + 10; struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { } }; typedef Point Vector; Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } bool operator == (const Point& a, const Point &b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } Point p[MAX_N << 1]; Point bound[3]; Point toy; int _count[MAX_N]; int n, m; void b_search() { int l = 0, r = n - 1, mid; while(l <= r) { mid = (l + r) >> 1; if(Cross(toy - p[mid], p[mid + n] - p[mid]) > 0) r = mid - 1; else if(Cross(toy - p[mid], p[mid + n] - p[mid]) < 0) l = mid + 1; } _count[r + 1]++; } int main() { //freopen("in.txt", "r", stdin); while(scanf("%d", &n), n) { memset(_count, 0, sizeof(_count)); scanf("%d", &m); scanf("%lf%lf%lf%lf", &bound[0].x, &bound[0].y, &bound[2].x, &bound[2].y); for(int i = 0; i < n; i++) { scanf("%lf%lf",&p[i].x, &p[i + n].x); p[i].y = bound[0].y; p[i + n].y = bound[2].y; } for(int i = 0; i < m; i++) { scanf("%lf%lf", &toy.x, &toy.y); b_search(); } for(int i = 0; i <= n; i++) printf("%d: %d\n", i, _count[i]); printf("\n"); } return 0; }