Codeforces Round #339 Div2 C: Peter and Snow Blower

問題

codeforces.com

解法

内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。

点と線分の距離を求めるライブラリ

double distanceVertex(pair<double, double> p1, pair<double, double> p2) {
  double dx = p1.first - p2.first;
  double dy = p1.second - p2.second;
  return sqrt(dx * dx + dy * dy);
}

double crossVector(pair<double, double> vl, pair<double, double> vr) {
  return vl.first * vr.second - vl.second * vr.first;
}
double dotVector(pair<double, double> vl, pair<double, double> vr) {
  return vl.first * vr.first + vl.second * vr.second;
}

double absVector(pair<double, double> v) {
  return sqrt(v.first * v.first + v.second * v.second);
}

double distanceDotAndLine(pair<double, double> P, pair<double, double> A,
                          pair<double, double> B) {
  pair<double, double> AB = {B.first - A.first, B.second - A.second};
  pair<double, double> BA = {A.first - B.first, A.second - B.second};
  pair<double, double> AP = {P.first - A.first, P.second - A.second};
  pair<double, double> BP = {P.first - B.first, P.second - B.second};

  if (dotVector(AB, AP) < 0.0) return absVector(AP);

  if (dotVector(BA, BP) < 0.0) return absVector(BP);

  double D = abs(crossVector(AB, AP));
  double L = distanceVertex(A, B);

  double H = D / L;
  return H;
}

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <string.h>

using namespace std;
typedef signed long long ll;

#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end())
typedef long long ll;
const double PI = 4 * atan(1.0);

double distanceVertex(pair<double, double> p1, pair<double, double> p2) {
  double dx = p1.first - p2.first;
  double dy = p1.second - p2.second;
  return sqrt(dx * dx + dy * dy);
}

double crossVector(pair<double, double> vl, pair<double, double> vr) {
  return vl.first * vr.second - vl.second * vr.first;
}
double dotVector(pair<double, double> vl, pair<double, double> vr) {
  return vl.first * vr.first + vl.second * vr.second;
}

double absVector(pair<double, double> v) {
  return sqrt(v.first * v.first + v.second * v.second);
}

double distanceDotAndLine(pair<double, double> P, pair<double, double> A,
                          pair<double, double> B) {
  pair<double, double> AB = {B.first - A.first, B.second - A.second};
  pair<double, double> BA = {A.first - B.first, A.second - B.second};
  pair<double, double> AP = {P.first - A.first, P.second - A.second};
  pair<double, double> BP = {P.first - B.first, P.second - B.second};

  if (dotVector(AB, AP) < 0.0) return absVector(AP);

  if (dotVector(BA, BP) < 0.0) return absVector(BP);

  double D = abs(crossVector(AB, AP));
  double L = distanceVertex(A, B);

  double H = D / L;
  return H;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, px, py;
  cin >> n >> px >> py;
  vector<pair<double, double>> vps(n);
  ll ma = 0;
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    vps[i] = {x, y};
    ll dx = x - px;
    ll dy = y - py;
    ll d = dx * dx + dy * dy;
    // cerr << d << endl;
    ma = max(ma, d);
  }

  double mi = 10000000000000.0;
  for (int i = 0; i < n - 1; ++i) {
    double dist = distanceDotAndLine({px, py}, vps[i], vps[i + 1]);
    mi = min(mi, dist);
  }
  double dist = distanceDotAndLine({px, py}, vps[n - 1], vps[0]);
  mi = min(dist, mi);
  printf("%.13lf\n", (ma - mi * mi) * PI);
}