Advertisement
Hippskill

Untitled

Jan 19th, 2016
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.86 KB | None | 0 0
  1.  
  2.  
  3. #include<stdio.h>
  4. #include<iostream>
  5. #include<vector>
  6. #include<cmath>
  7. #include<algorithm>
  8. #include<memory.h>
  9. #include<map>
  10. #include<set>
  11. #include<queue>
  12. #include<list>
  13. #include<sstream>
  14. #include<cstring>
  15. #include<numeric>
  16. using namespace std;
  17.  
  18. double const pi = 3.1415926535897932384;
  19.  
  20. const int N = 1e5;
  21.  
  22.  
  23. bool doubleEqual(double a, double b) {
  24.     return fabs(a - b) < 1e-9;
  25. }
  26.  
  27. bool doubleLess(double a, double b) {
  28.     return a < b && !doubleEqual(a, b);
  29. }
  30.  
  31. bool doubleLessOrEqual(double a, double b) {
  32.     return a < b || doubleEqual(a, b);
  33. }
  34.  
  35.  
  36. double mySqrt(double a) {
  37.     if (doubleLess(a, 0)) {
  38.         throw "sqrt(-1)";
  39.     }
  40.     if (a < 0) return 0;
  41.     return sqrt(a);
  42. }
  43.  
  44. double sqr(double a) {
  45.     return a * a;
  46. }
  47.  
  48. struct point {
  49. private: double x, y;
  50. public:
  51.     point() : x(0), y(0) {}
  52.     point(double x, double y) : x(x), y(y) {}
  53.  
  54.     void scan() {
  55.         scanf("%lf%lf", &x, &y);
  56.     }
  57.  
  58.     point operator+ (const point & P) const {
  59.         return point(x + P.x, y + P.y);
  60.     }
  61.  
  62.     point operator- (const point & P) const {
  63.         return point(x - P.x, y - P.y);
  64.     }
  65.  
  66.     point operator/ (double k) const {
  67.         return point(x / k, y / k);
  68.     }
  69.  
  70.     point operator*(double k) const {
  71.         return point(x * k, y * k);
  72.     }
  73.  
  74.     bool operator<(const point & P) const {
  75.         if (x != P.x) return x < P.x;
  76.         return y < P.y;
  77.     }
  78.  
  79.     double operator% (const point & P) const {
  80.         return x * P.x + y * P.y;
  81.     }
  82.  
  83.     double operator*(const point & p) const {
  84.         return x * p.y - y * p.x;
  85.     }
  86.  
  87.     double length() const {
  88.         return mySqrt(*this % *this);
  89.     }
  90.  
  91.     double val() {
  92.         return mySqrt(x * x + y * y);
  93.     }
  94.  
  95.     double dist(const point & P) const {
  96.         point r = P - *this;
  97.         return  r.val();
  98.     }
  99.  
  100.     point normalize(double k = 1) const
  101.     {
  102.         double len = length();
  103.         if (doubleEqual(len, 0)) {
  104.             if (doubleEqual(k, 0)) {
  105.                 return point();
  106.             }
  107.             //throw "zero-size vector";
  108.         }
  109.         return *this * (k / len);
  110.     }
  111.  
  112.     point getH(const point & A, const point & B) const {
  113.         point C = *this;
  114.         point v = B - A;
  115.         point u = C - A;
  116.         double k = v % u / v.length();
  117.         v = v.normalize(k);
  118.         point H = A + v;
  119.         return H;
  120.     }
  121.  
  122.     bool isOnLine(const point & A, const point & B) const {
  123.         return doubleEqual((A - *this) * (B - *this), 0);
  124.     }
  125.  
  126.     bool isInSegment(const point & A, const point & B) const {
  127.         return isOnLine(A, B) && doubleLessOrEqual((A - *this) % (B - *this), 0);
  128.     }
  129.  
  130. };
  131.  
  132. double triangleArea(point & A, point & B, point & C) {
  133.     return abs((A - B) * (C - B)) * 0.5;
  134. }
  135.  
  136.  
  137.  
  138.  
  139.  
  140. bool isIn(vector<point> P, point F) {
  141.     point M = (P[0] + P[2]) / 2;
  142.     double s = triangleArea(M, P[0], P[P.size() - 1]);
  143.     double s1 = triangleArea(F, P[0], P[P.size() - 1]);
  144.     for (int i = 1; i < P.size(); i++) {
  145.         s += triangleArea(M, P[i], P[i - 1]);
  146.         s1 += triangleArea(F, P[i], P[i - 1]);
  147.     }
  148.     return s1 <= s;
  149. }
  150.  
  151.  
  152. vector<point> a;
  153. point P;
  154.  
  155. double min(double a, double b, double c) {
  156.     return min(a, min(b, c));
  157. }
  158.  
  159. int main() {
  160. #ifndef ONLINE_JUDGE
  161.     freopen("input.txt", "r", stdin);
  162. #endif
  163.     int n;
  164.  
  165.     P.scan();
  166.     scanf("%d", &n);
  167.    
  168.     double md = HUGE_VAL;
  169.  
  170.     for (int i = 0; i < n; i++) {
  171.         a.push_back(point());
  172.         a[i].scan();
  173.     }
  174.  
  175.     for (int i = 1; i < n; i++) {
  176.         point H = P.getH(a[0], a[1]);
  177.         double d1 = P.dist(a[i]);
  178.         double d2 = P.dist(a[i - 1]);
  179.         if (P.isInSegment(a[i], a[i - 1])) {
  180.             printf("0.000");
  181.             return 0;
  182.         }
  183.         if (H.isInSegment(a[i], a[i - 1])) {
  184.             double d3 = P.dist(H);
  185.             md = min(md, min(d1, d2, d3));
  186.         }
  187.         else {
  188.             md = min(md, d1, d2);
  189.         }
  190.  
  191.     }
  192.     point H = P.getH(a[0], a[n - 1]);
  193.     double d1 = P.dist(a[0]);
  194.     double d2 = P.dist(a[n - 1]);
  195.     if (P.isInSegment(a[0], a[n - 1])) {
  196.         printf("0.000");
  197.         return 0;
  198.     }
  199.     if (H.isInSegment(a[0], a[n - 1])) {
  200.         double d3 = P.dist(H);
  201.         md = min(md, min(d1, d2, d3));
  202.     }
  203.     else {
  204.         md = min(md, d1, d2);
  205.     }
  206.  
  207.     if (isIn(a, P)) {
  208.         printf("0.000");
  209.         return 0;
  210.     }
  211.  
  212.     printf("%.3lf", md * 2);
  213.     return 0;
  214. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement