poj 2318 TOYS 点 直线 位置关系
题目描述：http://poj.org/problem?id=2318判断点与直线位置关系的题
#include <cstdio>#include <algorithm>using namespace std;struct point {int x,y;};struct line {point a,b;};int xmult(line seg, point p) {return (seg.b.x - p.x) * (seg.a.y - p.y) - (seg.a.x - p.x) * (seg.b.y - p.y);}bool comp(point p1, point p2) {if(p1.x != p2.x)return p1.x < p2.x;return p1.y < p2.y;}int main() {//freopen("in.txt", "r", stdin);int n, m;point lu, rl;point toys;line segs;int cnt;while(scanf("%d", &n) != EOF) {if(n == 0)break;for(int i = 0; i < n+ 1; i++)cnt = 0;scanf("%d %d %d %d %d", &m, &lu.x, &lu.y, &rl.x, &rl.y);segs.a = lu;segs.b.x = lu.x;segs.b.y = rl.y;segs.a.x = rl.x;segs.a.y = lu.y;segs.b = rl;int u, l;for(int i = 1; i <= n; i++) {scanf("%d %d", &u, &l);segs.a.x = u;segs.a.y = lu.y;segs.b.x = l;segs.b.y = rl.y;}for(int i = 0; i < m; i++)scanf("%d %d", &toys.x, &toys.y);int k = 0; sort(toys, toys + m, comp);for(int i = 0; i < m; i++) {for(int j = 0; j <= n; j++) { //避免重新从j = 0 开始搜索if(xmult(segs, toys) <= 0&& xmult(segs, toys) >= 0) {cnt++; k = j;//避免重新从j = 0 开始搜索break;}}}for(int i = 0; i <= n; i++)printf("%d: %d\n", i, cnt);printf("\n");}return 0;}
页:
[1]