山东省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

₁

 y

₁

 x

₂

 y

₂

 ... 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。

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

　　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代码：

 #include <stdio.h>
 #include <math.h>
 #include <string.h>
 #include <algorithm>
 #include <iostream>
 #include <string>
 #include <time.h>
 #include <queue>
 #include <list>
 #include <map>
 #include <set>
 #include <vector>
 #include <string.h>
 #define sf scanf
 #define pf printf
 #define lf double
 #define ll long long
 #define p123 printf("123\n");
 #define pn printf("\n");
 #define pk printf(" ");
 #define p(n) printf("%d",n);
 #define pln(n) printf("%d\n",n);
 #define s(n) scanf("%d",&n);
 #define ss(n) scanf("%s",n);
 #define ps(n) printf("%s",n);
 #define sld(n) scanf("%lld",&n);
 #define pld(n) printf("%lld",n);
 #define slf(n) scanf("%lf",&n);
 #define plf(n) printf("%lf",n);
 #define sc(n) scanf("%c",&n);
 #define pc(n) printf("%c",n);
 #define gc getchar();
 #define re(n,a) memset(n,a,sizeof(n));
 #define len(a) strlen(a)
 #define LL long long

 using namespace std;
 const double pi = 3.1415926535;
 /*
 https://codeforces.com/contest/1106/problems
 https://codeforces.com/contest/1106/submit
 */

 //2.6 随机素数测试和大数分解(POJ 1811)
 /* *************************************************
 * Miller_Rabin 算法进行素数测试
 * 速度快可以判断一个< 2^63 的数是不是素数
 **************************************************//*
 const int S = 8; //随机算法判定次数一般8∼10 就够了
 // 计算ret = (a*b)%c a,b,c < 2^63
 long long mult_mod(long long a,long long b,long long c) {
     a %= c;
     b %= c;
     long long ret = 0;
     long long tmp = a;
     while(b) {
         if(b & 1) {
             ret += tmp;
             if(ret > c)
                 ret -= c;//直接取模慢很多
         }
         tmp <<= 1;
         if(tmp > c)
             tmp -= c;
         b >>= 1;
     }
     return ret;
 }
 // 计算ret = (a^n)%mod
 long long pow_mod(long long a,long long n,long long mod) {
     long long ret = 1;
     long long temp = a%mod;
     while(n) {
         if(n & 1)
             ret = mult_mod(ret,temp,mod);
         temp = mult_mod(temp,temp,mod);
         n >>= 1;
     }
     return ret;
 }
 // 通过a^(n-1)=1(mod n)来判断n 是不是素数
 // n - 1 = x ∗ 2t 中间使用二次判断
 // 是合数返回true, 不一定是合数返回false
 bool check(long long a,long long n,long long x,long long t) {
     long long ret = pow_mod(a,x,n);
     long long last = ret;
     for(int i = 1; i <= t; i++) {
         ret = mult_mod(ret,ret,n);
         if(ret == 1 && last != 1 && last != n-1)
             return true;//合数
         last = ret;
     }
     if(ret != 1)
         return true;
     else
         return false;
 }
 //**************************************************
 // Miller_Rabin 算法
 // 是素数返回true,(可能是伪素数)
 // 不是素数返回false
 //**************************************************
 bool Miller_Rabin(long long n) {
     if( n < 2)
         return false;
     if( n == 2)
         return true;
     if( (n&1) == 0)
         return false;//偶数
     long long x = n - 1;
     long long t = 0;
     while( (x&1)==0 ) {
         x >>= 1;
         t++;
     }

     srand(time(NULL));/* *************** */
 /*
     for(int i = 0; i < S; i++) {
         long long a = rand()%(n-1) + 1;
         if( check(a,n,x,t) )
             return false;
     }
     return true;
 }
 */

 /*
 LL gcd(LL a,LL b) {
     if(a< b) {
         ll t =a;
         a =b;
         b = t;
     }
     if(b == 0) {
         return a;
     } else {
         return gcd(b,a%b);
     }
 }
 */#include<cstdio>
 #include<cmath>
 #include<algorithm>
 #define MAXN 110
 using namespace std;
 const double eps = 1e-;
 struct poi
 {
     double x,y;
     poi(double x = ,double y = ) :x(x),y(y) {}
 }pos[MAXN];
 typedef poi vec;
 vec operator +(vec A,vec B) {return vec(A.x + B.x, A.y + B.y);}
 vec operator -(vec A,vec B) {return vec(A.x - B.x, A.y - B.y);}
 vec operator *(vec A,double p) {return vec(A.x*p, A.y*p);}
 int dcmp(double x)//别打成bool
 {
     if(fabs(x) < eps) return ;
     else return x>?:-;
 }
 double cross(vec A,vec B) {return A.x*B.y - A.y*B.x;}
 double dot(vec A,vec B) {return A.x*B.x + A.y*B.y;}
 poi GetLineIntersection(poi A,vec v,poi B,vec w)
 {
     double t = cross(w,A - B) /cross(v,w);
     return A + v*t;
 }
 bool OnSegment(poi p,poi A,poi B)
 {
     //return dcmp(cross(A-p,B-p)) == 0&&dcmp(dot(A-p,B-p)) < 0; 不晓得这个为什么被卡了
     double mnx = min(A.x, B.x), mxx = max(A.x, B.x);
     double mny = min(A.y, B.y), mxy = max(A.y, B.y);
     return (mnx <= p.x + eps && p.x - eps <= mxx) && (mny <= p.y + eps && p.y - eps <= mxy);
 }
 struct polygon{
     poi a[MAXN];
     int sz;
 };
 polygon CutPolygon(polygon poly, poi A, poi B)
 {
     int m = ,n = poly.sz;
     polygon newpoly;
     for(int i = ; i < n; i++)
     {
         poi C = poly.a[i], D = poly.a[(i+)%n];
         if(dcmp(cross(B - A, C - A)) <= ) newpoly.a[m++] = C;//f**kf**kf**kf**kf**k,题目的边按顺时针给出,所以是<=
         if(dcmp(cross(B - A, C - D)) != ){
             poi ip = GetLineIntersection(A, B-A, C, D-C);
             if(OnSegment(ip, C, D)) newpoly.a[m++] = ip;
         }
     }
     newpoly.sz = m;
     return newpoly;
 }
 bool has_kernel(polygon poly)
 {
     polygon knl;
     knl.a[] = poi(-1e6,-1e6),knl.a[] = poi(1e6,-1e6),knl.a[] = poi(1e6,1e6),knl.a[] = poi(-1e6,1e6);//边界过大也要WA
     knl.sz = ;
     for(int i = ; i < poly.sz; i++)
     {
         poi A = poly.a[i], B = poly.a[(i+)%poly.sz];
         knl = CutPolygon(knl,A,B);
         if(knl.sz == ) return false;
     }
     return true;
 }
 int main()
 {
     polygon poly;
     int cas = ,n;
     int T = ;
     s(T )
     while(T --){
             s(n)

         for(int i = ; i < n; i++) scanf("%lf%lf",&poly.a[i].x,&poly.a[i].y);
         poly.sz = n;
         //printf("Floor #%d\n",++cas);
         if(has_kernel(poly)) printf("YES\n");
         else printf("NO\n");

     }
 }