题目描述: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[5005]; line segs[5005]; int cnt[5005]; while(scanf("%d", &n) != EOF) { if(n == 0) break; for(int i = 0; i < n + 1; i++) cnt[i] = 0; scanf("%d %d %d %d %d", &m, &lu.x, &lu.y, &rl.x, &rl.y); segs[0].a = lu; segs[0].b.x = lu.x; segs[0].b.y = rl.y; segs[n + 1].a.x = rl.x; segs[n + 1].a.y = lu.y; segs[n + 1].b = rl; int u, l; for(int i = 1; i <= n; i++) { scanf("%d %d", &u, &l); segs[i].a.x = u; segs[i].a.y = lu.y; segs[i].b.x = l; segs[i].b.y = rl.y; } for(int i = 0; i < m; i++) scanf("%d %d", &toys[i].x, &toys[i].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[j], toys[i]) <= 0 && xmult(segs[j + 1], toys[i]) >= 0) { cnt[j]++; k = j; //避免重新从j = 0 开始搜索 break; } } } for(int i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]); printf("\n"); } return 0; }
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj pku 1981 Circle and Points 点与圆 位置关系
2011-05-26 11:29 1261题目描述: http://poj.org/problem?id ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1211题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1026题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 871题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 883题目描述: http://acm.hdu.edu.cn/sh ... -
hdoj 1207 汉诺塔II dp 动态规划
2011-05-15 21:22 1666题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2506 Tiling 递推
2011-05-15 11:18 905题目描述: http://poj.org/problem?i ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1795题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1082题目描述: http://poj.org/problem?i ... -
poj 1012 Joseph
2011-05-10 17:42 1231题目描述:poj.org/problem?id=10 ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1131题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 798题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 713题目描述:http://www.poj.org/proble ... -
poj 1654 Area 多边形面积
2011-04-23 20:10 895题目描述:http://poj.org/proble ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 542题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 750题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 836题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1212题目描述:http://poj.org/problem?id= ...
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2653 计算几何算法初步模板,判断两直线是否相交。
poj分类poj分类poj分类poj分类
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1001答案
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
POJ2968代码有用,欢迎下载,POJ代码