山东省ACM多校联盟省赛个人训练第六场 poj 3335 D Rotating Scoreboard

山东省ACM多校联盟省赛个人训练第六场 D Rotating Scoreboard

时间限制：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

₁

₂

 ... x_n y_nwhere n (3 ≤ n ≤ 100) is the number of vertices in the polygon, and the pair of integers x_i y_i 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。

还是得多积累一些板子啊，不知道啥时候就用到了。

https://www.baidu.com/s?wd=%E5%A4%9A%E8%BE%B9%E5%BD%A2%E7%9A%84%E6%A0%B8&rsv_spt=1&rsv_iqid=0xb7bbe7b9000434df&issp=1&f=8&rsv_bp=1&rsv_idx=2&ie=utf-8&tn=baiduhome_pg&rsv_enter=1&rsv_sug3=14&rsv_sug1=8&rsv_sug7=100&rsv_sug2=0&inputT=4705&rsv_sug4=4705

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 }