题目描述: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=81
题目大意: n 边形的 n 个顶点按顺序给出, 接下来是m 个测试点, 对于每个测试点判断该点是否在多边形内(包括边界).
直接copy 浙大模板 O(∩_∩)O哈哈~
附上代码
#include <cstdio> #include <cmath> #include <cstdlib> #define offset 10000 #define eps 1e-8 #define zero(x) ( ((x > 0) ? (x) : (-x)) < eps ) struct point { double x,y; }; struct line { point a,b; }; 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); } //判点在任意多边形内,顶点按顺时针或逆时针给出 //on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限 int inside_polygon(point q,int n,point* p,int on_edge=1) { point q2; int i=0,count; while (i<n) for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset; i<n; i++) if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps) return on_edge; else if (zero(xmult(q,q2,p[i]))) break; else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps) count++; return count&1; } int main() { point p[101]; point q; int n, m; //多边形n 条边, m 个测试点 int k = 1; //第 k 个测试块儿,Problem k while(scanf("%d", &n) && n) { scanf("%d", &m); for(int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); if(k != 1) printf("\n"); printf("Problem %d:\n", k++); while(m--) { scanf("%lf %lf", &q.x, &q.y); int ans = inside_polygon(q, n, p, 2); //最后一个参数不小于1 即可 if(ans > 0) printf("Within\n"); else printf("Outside\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 1210题目描述: 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 1230题目描述:poj.org/problem?id=10 ... -
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 894题目描述:http://poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 663题目描述:http://poj.org/problem?id= ... -
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 835题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1212题目描述:http://poj.org/problem?id= ...
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢
zoj 1002 C语言的为什么描述要这么多字啊。。
能AC 通过的c++代码,包括zoj1002,1091,1789