How I Mathematician Wonder What You Are!
问题描述 :
After counting so many stars in the sky in his childhood, Isaac, now an astronomer and a mathematician uses a big astronomical telescope and lets his image processing program count stars. The hardest part of the program is to judge if shining object in the sky is really a star. As a mathematician, the only way he knows is to apply a mathematical definition of stars.
The mathematical definition of a star shape is as follows: A planar shape F is star-shaped if and only if there is a point C ∈ F such that, for any point P ∈ F, the line segment CP is contained in F. Such a point C is called a center of F. To get accustomed to the definition let’s see some examples below.
The first two are what you would normally call stars. According to the above definition, however, all shapes in the first row are star-shaped. The two in the second row are not. For each star shape, a center is indicated with a dot. Note that a star shape in general has infinitely many centers. Fore Example, for the third quadrangular shape, all points in it are centers.
Your job is to write a program that tells whether a given polygonal shape is star-shaped or not.
输入:
The input is a sequence of datasets followed by a line containing a single zero. Each dataset specifies a polygon, and is formatted as follows.
n x1 y1 x2 y2 …
xn yn
The first line is the number of vertices, n, which satisfies 4 ≤ n ≤ 50. Subsequent n lines are the x- and y-coordinates of the n vertices. They are integers and satisfy 0 ≤ xi ≤ 10000 and 0 ≤ yi ≤ 10000 (i = 1, …, n). Line segments (xi, yi)–(xi + 1, yi + 1) (i = 1, …, n − 1) and the line segment (xn, yn)–(x1, y1) form the border of the polygon in the counterclockwise order. That is, these line segments see the inside of the polygon in the left of their directions.
You may assume that the polygon is simple, that is, its border never crosses or touches itself. You may assume assume that no three edges of the polygon meet at a single point even when they are infinitely extended.
输出:
For each dataset, output “1
” if the polygon is star-shaped and “0
” otherwise. Each number must be in a separate line and the line should not contain any other characters.
样例输入:
6 66 13 96 61 76 98 13 94 4 0 45 68 8 27 21 55 14 93 12 56 95 15 48 38 46 51 65 64 31 0
样例输出:
1 0
import java.util.Scanner; public class Main { static double x[], y[]; static double tx[], ty[]; static double txp[], typ[]; static int num; static int tnum; static double a, b, c; public static void main(String[] args) { Scanner scan = new Scanner(System.in); while (true) { int n = scan.nextInt(); if (n == 0) break; num = n; x = new double[100]; y = new double[100]; tx = new double[100]; ty = new double[100]; txp = new double[100]; typ = new double[100]; for (int i = 0; i < n; i++) { x[i] = scan.nextDouble(); y[i] = scan.nextDouble(); tx[i + 1] = x[i]; ty[i + 1] = y[i]; } x[n] = x[0]; y[n] = y[0]; tx[0] = tx[n]; ty[0] = ty[n]; tx[n + 1] = tx[1]; ty[n + 1] = ty[1]; for (int i = 0; i < n; i++) { a = y[i + 1] - y[i]; //求直线aX+bY+c=0的参数a,b,c b = x[i] - x[i + 1]; c = x[i + 1] * y[i] - x[i] * y[i + 1]; solve(); } if (num == 0) System.out.println("0"); else System.out.println("1"); } } public static void solve() { tnum = 0; for (int i = 1; i <= num; i++) { if (sig(a * tx[i] + b * ty[i] + c) <= 0) { // 在一侧 txp[tnum] = tx[i]; typ[tnum++] = ty[i]; } else { // 在另一侧 if (sig(a * tx[i - 1] + b * ty[i - 1] + c) < 0) //小于0才会有交点 insert(tx[i - 1], ty[i - 1], tx[i], ty[i]); if (sig(a * tx[i + 1] + b * ty[i + 1] + c )< 0) insert(tx[i + 1], ty[i + 1], tx[i], ty[i]); } } num = tnum; //更新 num,tx,ty for (int j = 1; j <= num; j++) { tx[j] = txp[j - 1]; ty[j] = typ[j - 1]; } tx[0] = tx[num]; ty[0] = ty[num]; tx[num + 1] = tx[1]; ty[num + 1] = ty[1]; } private static int sig(double d) { if(d< 1e-10) return -1; else if(d>1e-10) return 1; return 0; } //求两直线交点 其中一条直线 已经表示成ax+by+c=0, 另一直线 是两个点 public static void insert(double x1, double y1, double x2, double y2) { double xx = Math.abs(a * x1 + b * y1 + c); double yy = Math.abs(a * x2 + b * y2 + c); txp[tnum] = (x1 * yy + x2 * xx) / (xx + yy); typ[tnum++] = (y1 * yy + y2 * xx) / (xx + yy); } }
来自:ACM之家
www.acmerblog.com
相关推荐
北大POJ初级-计算几何学 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ1048,加强版的约瑟夫问题 难度中等
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
用java的biginteger实现的poj1001,比较简单的方法
POJ 1328 java做!雷达问题!java版本!AC答案~
NULL 博文链接:https://128kj.iteye.com/blog/1744222
北大POJ2002-Squares 解题报告+AC代码
北大poj JAVA源码
提示:二叉树遍历而已,给出前序和中序,求后序 解题思路 1、前序遍历的第一个字母必是 根 2、在中序遍历的字母串中找出 根字母,那么根字母左右两边的字符串就分别是它的左、右子树 3、利用递归复原二叉树(把...
poj 2785 4 Values whose Sum is 0 测试数据 解题报告: http://blog.csdn.net/qq7366020/article/details/8623208
NULL 博文链接:https://128kj.iteye.com/blog/1749213
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
poj 2653 计算几何算法初步模板,判断两直线是否相交。
1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1.13 矢量运算求几何模板 35 ...
poj题目分类 POJ(Princeton Online Judge)是一個在线编程平台,为编程爱好者和学生提供了大量的...这些知识点涵盖了算法、数据结构、数学、计算几何学等领域的多个方面,为编程爱好者和学生提供了广泛的知识基础。
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类