题目链接：http://poj.org/problem?id=2318
水水的一道题哇！（来熟悉模板， 哈哈）
判断toys的位置。
思路很简单，叉乘就可以知道点与直线的关系；比如xmult（point p1, point p2, point p0）>0 p1在直线的左侧（p2，p0是直线的端点，左右理解为眼睛顺着直线的方向的左右）。
#include <iostream> #include <algorithm> #include <fstream> #include <iomanip> #include <cstdio> #include <vector> #include <cstring> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; struct point { int x, y; }; struct line { point a, b; }l[5050]; int mp[5050]; double xmult(point p1, point p2, point p0) { return (p1.x- p0.x)* (p2.y- p0.y)- (p2.x- p0.x)* (p1.y- p0.y); } int main() { int n, m, x1, x2, y1, y2; while(scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2)== 6 && n) { memset(mp, 0, sizeof(mp)); for(int i= 0; i< n; i++) { int u, v; scanf("%d%d", &u, &v); point p, q; p.x= u; p.y= y1; q.x= v; q.y= y2; l[i].a= p; l[i].b= q; } for(int i= 0; i< m; i++) { point p; scanf("%d%d", &p.x, &p.y); int ans= 0; for(int j= 0; j< n; j++) if(xmult(p, l[j].a, l[j].b)> 0) ans++; mp[ans]++; } for(int i= 0; i<= n; i++) printf("%d: %d\n", i, mp[i]); printf("\n"); } return 0; }
