Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<iostream>
- #include<vector>
- #include<cmath>
- #include<algorithm>
- #include<memory.h>
- #include<map>
- #include<set>
- #include<queue>
- #include<list>
- #include<sstream>
- #include<cstring>
- #include<numeric>
- using namespace std;
- double const pi = 3.1415926535897932384;
- const int N = 1e5;
- bool doubleEqual(double a, double b) {
- return fabs(a - b) < 1e-9;
- }
- bool doubleLess(double a, double b) {
- return a < b && !doubleEqual(a, b);
- }
- bool doubleLessOrEqual(double a, double b) {
- return a < b || doubleEqual(a, b);
- }
- double mySqrt(double a) {
- if (doubleLess(a, 0)) {
- throw "sqrt(-1)";
- }
- if (a < 0) return 0;
- return sqrt(a);
- }
- double sqr(double a) {
- return a * a;
- }
- struct point {
- private: double x, y;
- public:
- point() : x(0), y(0) {}
- point(double x, double y) : x(x), y(y) {}
- void scan() {
- scanf("%lf%lf", &x, &y);
- }
- point operator+ (const point & P) const {
- return point(x + P.x, y + P.y);
- }
- point operator- (const point & P) const {
- return point(x - P.x, y - P.y);
- }
- point operator/ (double k) const {
- return point(x / k, y / k);
- }
- point operator*(double k) const {
- return point(x * k, y * k);
- }
- bool operator<(const point & P) const {
- if (x != P.x) return x < P.x;
- return y < P.y;
- }
- double operator% (const point & P) const {
- return x * P.x + y * P.y;
- }
- double operator*(const point & p) const {
- return x * p.y - y * p.x;
- }
- double length() const {
- return mySqrt(*this % *this);
- }
- double val() {
- return mySqrt(x * x + y * y);
- }
- double dist(const point & P) const {
- point r = P - *this;
- return r.val();
- }
- point normalize(double k = 1) const
- {
- double len = length();
- if (doubleEqual(len, 0)) {
- if (doubleEqual(k, 0)) {
- return point();
- }
- //throw "zero-size vector";
- }
- return *this * (k / len);
- }
- point getH(const point & A, const point & B) const {
- point C = *this;
- point v = B - A;
- point u = C - A;
- double k = v % u / v.length();
- v = v.normalize(k);
- point H = A + v;
- return H;
- }
- bool isOnLine(const point & A, const point & B) const {
- return doubleEqual((A - *this) * (B - *this), 0);
- }
- bool isInSegment(const point & A, const point & B) const {
- return isOnLine(A, B) && doubleLessOrEqual((A - *this) % (B - *this), 0);
- }
- };
- double triangleArea(point & A, point & B, point & C) {
- return abs((A - B) * (C - B)) * 0.5;
- }
- bool isIn(vector<point> P, point F) {
- point M = (P[0] + P[2]) / 2;
- double s = triangleArea(M, P[0], P[P.size() - 1]);
- double s1 = triangleArea(F, P[0], P[P.size() - 1]);
- for (int i = 1; i < P.size(); i++) {
- s += triangleArea(M, P[i], P[i - 1]);
- s1 += triangleArea(F, P[i], P[i - 1]);
- }
- return s1 <= s;
- }
- vector<point> a;
- point P;
- double min(double a, double b, double c) {
- return min(a, min(b, c));
- }
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- #endif
- int n;
- P.scan();
- scanf("%d", &n);
- double md = HUGE_VAL;
- for (int i = 0; i < n; i++) {
- a.push_back(point());
- a[i].scan();
- }
- for (int i = 1; i < n; i++) {
- point H = P.getH(a[0], a[1]);
- double d1 = P.dist(a[i]);
- double d2 = P.dist(a[i - 1]);
- if (P.isInSegment(a[i], a[i - 1])) {
- printf("0.000");
- return 0;
- }
- if (H.isInSegment(a[i], a[i - 1])) {
- double d3 = P.dist(H);
- md = min(md, min(d1, d2, d3));
- }
- else {
- md = min(md, d1, d2);
- }
- }
- point H = P.getH(a[0], a[n - 1]);
- double d1 = P.dist(a[0]);
- double d2 = P.dist(a[n - 1]);
- if (P.isInSegment(a[0], a[n - 1])) {
- printf("0.000");
- return 0;
- }
- if (H.isInSegment(a[0], a[n - 1])) {
- double d3 = P.dist(H);
- md = min(md, min(d1, d2, d3));
- }
- else {
- md = min(md, d1, d2);
- }
- if (isIn(a, P)) {
- printf("0.000");
- return 0;
- }
- printf("%.3lf", md * 2);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement