Codeforces Round #339 Div2 C: Peter and Snow Blower
解法
内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。
点と線分の距離を求めるライブラリ
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); }