poj 3335 Rotating Scoreboard
Posted on 2015年1月13日 19:261 2 3 4 5 6 7 | /****************************************\* Author : ztx* Title : poj 3335 Rotating Scoreboard* ALG : 计算几何 半平面交 多边形内核* CMT : 这是一个n^n算法* Time :\****************************************/ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | /****************************************\* Author : ztx* Title : poj 3335 Rotating Scoreboard* ALG : 计算几何 半平面交 多边形内核* CMT :* Time :\****************************************/#include <cstdio>#define maxn 105LLstruct POINT { double x , y ; POINT operator - (const POINT& b) const { return (POINT){x-b.x , y-b.y} ; } int operator * (const POINT& b) const { return x*b.y-y*b.x ; }} p[maxn] , sta[maxn] , points[maxn] ;/* points[]存储原数据 , sta缓存 , p为已经存在的半平面交的顶点 */typedef POINT VECTOR ;VECTOR Vector(POINT from , POINT to) { return to-from ; }int n , size , top ;POINT Intersect(POINT a , POINT b , POINT c , POINT d) { /* 传进四个点时,保证有交点 */ POINT ret ; if (a.x == b.x) { ret.x = a.x ; ret.y = (c.y+d.y)/2.0 ; } else if (c.x == d.x) { ret.x = c.x ; ret.y = (a.y+b.y)/2.0 ; } else { ret.x = ((c.x-d.x)*(a.y*b.x-a.x*b.y)-(a.x-b.x)*(c.y*d.x-c.x*d.y)) /((d.y-c.y)*(a.x-b.x)-(b.y-a.y)*(c.x-d.x)) ; ret.y = (ret.x*(b.y-a.y)+a.y*b.x-a.x*b.y)/(b.x-a.x) ; } return ret ;}int Direct(POINT from , POINT to , POINT p) { int tmp = (to-from)*(p-to) ; if (tmp < 0) return -1 ; else return tmp > 0 ; /* 左侧为1 , 同向为0 , 右侧为-1 */}void Cut(POINT a , POINT b) {int i ; top = 0 ; for (i = 1 ; i <= size ; i ++ ) { /* 若点以顺时针给出 */ if (Direct(a , b , p[i]) <= 0) sta[++top] = p[i] ; else { if (Direct(a , b , p[i-1]) < 0) sta[++top] = Intersect(a , b , p[i-1] , p[i]) ; if (Direct(a , b , p[i+1]) < 0) sta[++top] = Intersect(a , b , p[i] , p[i+1]) ; } } for (i = 1 ; i <= top ; i ++ ) p[i] = sta[i] ; p[0] = p[top] ; p[top+1] = p[1] ; size = top ;}bool Solve() { for (int i = 1 ; i <= n ; i ++ ) Cut(points[i] , points[i+1]) ; return size > 0 ;}int main() {int T , i ;// #define READ #ifdef READ freopen(".in" ,"r",stdin ) ; freopen(".out","w",stdout) ; #endif scanf("%d", &T ) ; while (T --) { scanf("%d", &n ) ; for (i = 1 ; i <= n ; i ++ ) scanf("%lf%lf", &points[i].x , &points[i].y) ; points[n+1] = points[1] ; points[0] = points[n] ; for (i = n+1 ; i >= 0 ; i -- ) p[i] = points[i] ; size = n ; if (Solve()) puts("YES") ; else puts("NO") ; } #ifdef READ fclose(stdin) ; fclose(stdout) ; #else getchar() ; getchar() ; #endif return 0 ;} |