Codeforces Round #339 (Div. 1) A. Peter and Snow Blower

,

A. Peter and Snow Blower

解法

中心$P$と最も近い点を$Q$、遠い点を$R$とすると、$\pi |R - P|^2 - \pi |Q - P|^2$である。ただし、最も近い点$Q$は多角形の頂点とは限らないので注意。点と線分の距離の計算が必要。

実装

spaghetti sourceは最高。

#include <iostream>
#include <vector>
#include <cstdio>
#include <complex>
#include <cmath>
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

// http://www.prefield.com/algorithm/
const double EPS = 1e-8;
typedef complex<double> P;
namespace std {
    bool operator < (const P& a, const P& b) {
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
}
double cross(const P& a, const P& b) {
    return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
    return real(conj(a)*b);
}
struct L : public vector<P> {
    L(const P &a, const P &b) {
        push_back(a); push_back(b);
    }
};
bool intersectSP(const L &s, const P &p) {
      return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}
P projection(const L &l, const P &p) {
  double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}
double distanceSP(const L &s, const P &p) {
  const P r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s[0] - p), abs(s[1] - p));
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; double px, py; cin >> n >> px >> py;
    P p = { px, py };
    vector<P> qs(n);
    repeat (i,n) {
        double qx, qy; cin >> qx >> qy;
        qs[i] = { qx, qy };
    }
    double a = INFINITY, b = 0;
    repeat (i,n) {
        int j = (i+1)%n;
        b = max(b, abs(qs[i] - p));
        a = min(a, abs(qs[i] - p));
        a = min(a, distanceSP(L(qs[i], qs[j]), p));
    }
    printf("%.16lf\n", double(M_PI * (b*b - a*a)));
    return 0;
}