【POJ 3335】多邊形的核

1.​​題目連結​​。題目大意：給定一個多邊形，是不是在這個多邊形的内部存在一個點使得站在這個點可以看到多邊形中的任意一個點。

#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstring>
using namespace std;
#pragma warning(disable:4996)
struct node
{
  double x;
  double y;
} p[110], temp[110], newp[110];//p是最開始的多邊形的每個點，temp是中間過程中臨時存的多邊形的每個點，newp是切割後的多邊形的每個點
int n, newn;//原來的點數，切割後的點數
//直線方程的三個系數
double a, b, c;
void getline(node x, node y)//求x與y兩點确定的直線方程ax+by+c=0
{
  a = y.y - x.y;
  b = x.x - y.x;
  c = y.x*x.y - y.y*x.x;
}
node intersect(node x, node y)//求x與y點确定的直線與ax+by+c=0這條直線的交點
{
  double u = a * x.x + b * x.y + c;
  double v = a * y.x + b * y.y + c;
  node t;
  t.x = (x.x*v + y.x*u) / (u + v);//y.y-x.y=u+v;y.y-t.y=v;y.y-x.y=u;
  t.y = (x.y*v + y.y*u) / (u + v);
  return t;
}
void cut()
{
  int cutn = 0;
  for (int i = 1; i <= newn; i++)
  {
    if (a*newp[i].x + b * newp[i].y + c >= 0)//所有的點都大于0，說明所有的點都在這條直線的另一邊，是以不用切
      temp[++cutn] = newp[i];
    else
    {
      if (a*newp[i - 1].x + b * newp[i - 1].y + c > 0)
        temp[++cutn] = intersect(newp[i - 1], newp[i]);//把新交點加入
      if (a*newp[i + 1].x + b * newp[i + 1].y + c > 0)
        temp[++cutn] = intersect(newp[i + 1], newp[i]);
    }
  }
  for (int i = 1; i <= cutn; i++)
    newp[i] = temp[i];
  newp[cutn + 1] = temp[1];//能夠找出所有點的前驅和後繼
  newp[0] = temp[cutn];
  newn = cutn;
}

void solve()
{
  for (int i = 1; i <= n; i++)
  {
    newp[i] = p[i];
  }
  p[n + 1] = p[1];
  newp[n + 1] = newp[1];
  newp[0] = newp[n];
  newn = n;
  for (int i = 1; i <= n; i++)
  {
    getline(p[i], p[i + 1]);//從頭開始順序周遊兩個相鄰點。
    cut();
  }

}
int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      scanf("%lf %lf", &p[i].x, &p[i].y);
    solve();
    if (newn == 0) puts("NO");
    else
      puts("YES");
  }
  return 0;
}