山东省ACM多校联盟省赛个人训练第六场 poj 3335 D Rotating Scoreboard
山东省ACM多校联盟省赛个人训练第六场 D Rotating Scoreboard
https://vjudge.net/problem/POJ-3335
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
This year, ACM/ICPC World finals will be held in a hall in form of a simple polygon. The coaches and spectators are seated along the edges of the polygon. We want to place a rotating scoreboard somewhere in the hall such that a spectator sitting anywhere on the boundary of the hall can view the scoreboard (i.e., his line of sight is not blocked by a wall). Note that if the line of sight of a spectator is tangent to the polygon boundary (either in a vertex or in an edge), he can still view the scoreboard. You may view spectator's seats as points along the boundary of the simple polygon, and consider the scoreboard as a point as well. Your program is given the corners of the hall (the vertices of the polygon), and must check if there is a location for the scoreboard (a point inside the polygon) such that the scoreboard can be viewed from any point on the edges of the polygon.
输入描述:
The first line contains three integers N, M, G(0 < N, M ≤ 500, 0 ≤ G ≤ 200).
Each of the following N lines contains M integers, representing the matrix. It is guaranteed that every integer in the matrix is in the range [-100, 100].
输出描述:
Output the maximum L in a single line.The first number in the input line, T is the number of test cases. Each test case is specified on a single line of input in the form n x
1
y
1
x
2
y
2
... xn ynwhere n (3 ≤ n ≤ 100) is the number of vertices in the polygon, and the pair of integers xi yi sequence specify the vertices of the polygon sorted in order.
示例1
输入
2 4 0 0 0 1 1 1 1 0 8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
输出
YES NO
分析
题目的意思就是在一个多边形的各个角上看整个区域，会不会有一个区域可以被所有的点都看到，或者反过来说可不可以找到一个点当做光源，使得这个光源发出的光各个点都能看到。
如果对平面几何有所了解的话，会立刻意识到这是多边形的核。
可惜我不是大神，我只是知道，这个东西是一个模板，而且我见过，这个模板叫啥，不知道，怎么用，不知道，用途是啥，不知道(否认三连)。
从网上超级容易直接就找到了教程和模板（之前做过类似的题目），直接使用AC掉本题一血并AK。
还是得多积累一些板子啊，不知道啥时候就用到了。
AC代码：
1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <string> 7 #include <time.h> 8 #include <queue> 9 #include <list> 10 #include <map> 11 #include <set> 12 #include <vector> 13 #include <string.h> 14 #define sf scanf 15 #define pf printf 16 #define lf double 17 #define ll long long 18 #define p123 printf("123\n"); 19 #define pn printf("\n"); 20 #define pk printf(" "); 21 #define p(n) printf("%d",n); 22 #define pln(n) printf("%d\n",n); 23 #define s(n) scanf("%d",&n); 24 #define ss(n) scanf("%s",n); 25 #define ps(n) printf("%s",n); 26 #define sld(n) scanf("%lld",&n); 27 #define pld(n) printf("%lld",n); 28 #define slf(n) scanf("%lf",&n); 29 #define plf(n) printf("%lf",n); 30 #define sc(n) scanf("%c",&n); 31 #define pc(n) printf("%c",n); 32 #define gc getchar(); 33 #define re(n,a) memset(n,a,sizeof(n)); 34 #define len(a) strlen(a) 35 #define LL long long 36 37 using namespace std; 38 const double pi = 3.1415926535; 39 /* 40 https://codeforces.com/contest/1106/problems 41 https://codeforces.com/contest/1106/submit 42 */ 43 44 //2.6 随机素数测试和大数分解(POJ 1811) 45 /* ************************************************* 46 * Miller_Rabin 算法进行素数测试 47 * 速度快可以判断一个< 2^63 的数是不是素数 48 **************************************************//* 49 const int S = 8; //随机算法判定次数一般8∼10 就够了 50 // 计算ret = (a*b)%c a,b,c < 2^63 51 long long mult_mod(long long a,long long b,long long c) { 52 a %= c; 53 b %= c; 54 long long ret = 0; 55 long long tmp = a; 56 while(b) { 57 if(b & 1) { 58 ret += tmp; 59 if(ret > c) 60 ret -= c;//直接取模慢很多 61 } 62 tmp <<= 1; 63 if(tmp > c) 64 tmp -= c; 65 b >>= 1; 66 } 67 return ret; 68 } 69 // 计算ret = (a^n)%mod 70 long long pow_mod(long long a,long long n,long long mod) { 71 long long ret = 1; 72 long long temp = a%mod; 73 while(n) { 74 if(n & 1) 75 ret = mult_mod(ret,temp,mod); 76 temp = mult_mod(temp,temp,mod); 77 n >>= 1; 78 } 79 return ret; 80 } 81 // 通过a^(n-1)=1(mod n)来判断n 是不是素数 82 // n - 1 = x ∗ 2t 中间使用二次判断 83 // 是合数返回true, 不一定是合数返回false 84 bool check(long long a,long long n,long long x,long long t) { 85 long long ret = pow_mod(a,x,n); 86 long long last = ret; 87 for(int i = 1; i <= t; i++) { 88 ret = mult_mod(ret,ret,n); 89 if(ret == 1 && last != 1 && last != n-1) 90 return true;//合数 91 last = ret; 92 } 93 if(ret != 1) 94 return true; 95 else 96 return false; 97 } 98 //************************************************** 99 // Miller_Rabin 算法 100 // 是素数返回true,(可能是伪素数) 101 // 不是素数返回false 102 //************************************************** 103 bool Miller_Rabin(long long n) { 104 if( n < 2) 105 return false; 106 if( n == 2) 107 return true; 108 if( (n&1) == 0) 109 return false;//偶数 110 long long x = n - 1; 111 long long t = 0; 112 while( (x&1)==0 ) { 113 x >>= 1; 114 t++; 115 } 116 117 srand(time(NULL));/* *************** */ 118 /* 119 for(int i = 0; i < S; i++) { 120 long long a = rand()%(n-1) + 1; 121 if( check(a,n,x,t) ) 122 return false; 123 } 124 return true; 125 } 126 */ 127 128 /* 129 LL gcd(LL a,LL b) { 130 if(a< b) { 131 ll t =a; 132 a =b; 133 b = t; 134 } 135 if(b == 0) { 136 return a; 137 } else { 138 return gcd(b,a%b); 139 } 140 } 141 */#include<cstdio> 142 #include<cmath> 143 #include<algorithm> 144 #define MAXN 110 145 using namespace std; 146 const double eps = 1e-6; 147 struct poi 148 { 149 double x,y; 150 poi(double x = 0,double y = 0) :x(x),y(y) {} 151 }pos[MAXN]; 152 typedef poi vec; 153 vec operator +(vec A,vec B) {return vec(A.x + B.x, A.y + B.y);} 154 vec operator -(vec A,vec B) {return vec(A.x - B.x, A.y - B.y);} 155 vec operator *(vec A,double p) {return vec(A.x*p, A.y*p);} 156 int dcmp(double x)//别打成bool 157 { 158 if(fabs(x) < eps) return 0; 159 else return x>0?1:-1; 160 } 161 double cross(vec A,vec B) {return A.x*B.y - A.y*B.x;} 162 double dot(vec A,vec B) {return A.x*B.x + A.y*B.y;} 163 poi GetLineIntersection(poi A,vec v,poi B,vec w) 164 { 165 double t = cross(w,A - B) /cross(v,w); 166 return A + v*t; 167 } 168 bool OnSegment(poi p,poi A,poi B) 169 { 170 //return dcmp(cross(A-p,B-p)) == 0&&dcmp(dot(A-p,B-p)) < 0; 不晓得这个为什么被卡了 171 double mnx = min(A.x, B.x), mxx = max(A.x, B.x); 172 double mny = min(A.y, B.y), mxy = max(A.y, B.y); 173 return (mnx <= p.x + eps && p.x - eps <= mxx) && (mny <= p.y + eps && p.y - eps <= mxy); 174 } 175 struct polygon{ 176 poi a[MAXN]; 177 int sz; 178 }; 179 polygon CutPolygon(polygon poly, poi A, poi B) 180 { 181 int m = 0,n = poly.sz; 182 polygon newpoly; 183 for(int i = 0; i < n; i++) 184 { 185 poi C = poly.a[i], D = poly.a[(i+1)%n]; 186 if(dcmp(cross(B - A, C - A)) <= 0) newpoly.a[m++] = C;//f**kf**kf**kf**kf**k,题目的边按顺时针给出,所以是<= 187 if(dcmp(cross(B - A, C - D)) != 0){ 188 poi ip = GetLineIntersection(A, B-A, C, D-C); 189 if(OnSegment(ip, C, D)) newpoly.a[m++] = ip; 190 } 191 } 192 newpoly.sz = m; 193 return newpoly; 194 } 195 bool has_kernel(polygon poly) 196 { 197 polygon knl; 198 knl.a[0] = poi(-1e6,-1e6),knl.a[1] = poi(1e6,-1e6),knl.a[2] = poi(1e6,1e6),knl.a[3] = poi(-1e6,1e6);//边界过大也要WA 199 knl.sz = 4; 200 for(int i = 0; i < poly.sz; i++) 201 { 202 poi A = poly.a[i], B = poly.a[(i+1)%poly.sz]; 203 knl = CutPolygon(knl,A,B); 204 if(knl.sz == 0) return false; 205 } 206 return true; 207 } 208 int main() 209 { 210 polygon poly; 211 int cas = 0,n; 212 int T = 0; 213 s(T ) 214 while(T --){ 215 s(n) 216 217 for(int i = 0; i < n; i++) scanf("%lf%lf",&poly.a[i].x,&poly.a[i].y); 218 poly.sz = n; 219 //printf("Floor #%d\n",++cas); 220 if(has_kernel(poly)) printf("YES\n"); 221 else printf("NO\n"); 222 223 } 224 }
