Peter and Snow Blower

题目描述

Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.

Formally, we assume that Peter’s machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.

Peter decided to tie his car to point $P$ and now he is wondering what is the area of the region that will be cleared from snow. Help him.

题意概述

在平面直角坐标系内有一个$n$边形，按顺时针给定它的所有顶点。现给定一个点$P$，求$n$边形绕着点$P$旋转一周所能扫到的面积。

数据范围：$3 \le n \le 10^5$。

算法分析

可以发现$n$边形扫过的图形是一个环形（或圆）。也就是说，我们只要分别求出这个图形最大和最小的半径，就可以算出面积。显然，最大的半径就是$n$边形中距离点$P$最远的点到点$P$的距离。最小的半径有两种可能：① 距离点$P$最近的点到点$P$的距离；② 距离点$P$最近的边到点$P$的距离（要求点$P$在这条边上的投影在这条边上）。可以用向量乘法判断点$P$的投影是否在某条边上，用点到直线距离公式求点$P$到某条边的距离，用两点间距离公式求点$P$到某个点的距离。

代码

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const long double pi = 3.1415926535898;
struct point {
  long double x, y;
} p[100001];
long double x, y, ma, mi = 1e18;
long long n;
long double get_dist(int s) {
  int t = s + 1;
  if (t > n) t = 1;
  if (p[s].x == p[t].x) return abs(p[s].x);
  long double a = (p[t].y - p[s].y) / (p[t].x - p[s].x), b = -1, c = a * p[s].x - p[s].y;
  return abs(c) / sqrt(a * a + b * b);
}
long double check(int s) {
  int t = s + 1;
  if (t > n) t = 1;
  long double x1 = p[s].x, y1 = p[s].y, x2 = p[t].x, y2 = p[t].y;
  long double p = x1 * (x2 - x1) + y1 * (y2 - y1), q = x2 * (x1 - x2) + y2 * (y1 - y2);
  if (p < 0 && q < 0) return get_dist(s) * get_dist(s);
  else if (p >= 0) return x1 * x1 + y1 * y1;
  else return x2 * x2 + y2 * y2;
}
bool in() {
  bool ret = false;
  for (long long i = 1, j = n; i <= n; j = i++)
    if (((p[i].y > y) != (p[j].y > y)) && ((p[i].x - p[j].x) * p[i].y / (p[j].y - p[i].y) + p[i].x) > 0)
      ret = !ret;
  return ret;
}
int main()
{
  cin >> n >> x >> y;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i].x >> p[i].y; p[i].x -= x, p[i].y -= y;
    ma = max(ma, p[i].x * p[i].x + p[i].y * p[i].y);
    if (i > 1) mi = min(mi, check(i - 1));
  }
  mi = min(mi, check(n)); if (in()) mi = 0;
  cout << setprecision(10) << fixed << (ma - mi) * pi << endl;
  return 0;
}