niyaznigmatullin

Untitled

Feb 15th, 2016
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <vector>
  6. #include <cstdlib>
  7. #include <utility>
  8. #include <memory.h>
  9. #include <iterator>
  10. #include <iomanip>
  11. #include <queue>
  12. #include <ctime>
  13. #include <deque>
  14. #include <set>
  15. #include <map>
  16.  
  17. #define move mov_e
  18.  
  19. using namespace std;
  20.  
  21. #define pb push_back
  22. #define mp make_pair
  23. #define F first
  24. #define S second
  25.  
  26. typedef long double ld;
  27.  
  28. const ld eps = 1e-7L;
  29. const ld INF = 1e9L;
  30.  
  31.  
  32. int n;
  33.  
  34. struct pt {
  35.     ld x, y;
  36.     pt () {};
  37.     pt (ld x, ld y) {
  38.         this -> x = x;
  39.         this -> y = y;
  40.     }
  41.     pt operator - (const pt &p) {
  42.         return pt(x - p.x, y - p.y);
  43.     }
  44.     pt mult(ld C) {
  45.         return pt(x * C, y * C);
  46.     }
  47.     pt operator + (const pt &p) {
  48.         return pt(x + p.x, y + p.y);
  49.     }
  50.     ld getLen() {
  51.         return sqrt(x * x + y * y);
  52.     }
  53.     bool operator< (const pt & p) const {
  54.         return (x < p.x-eps) || (abs(x-p.x) < eps && y < p.y - eps);
  55.     }
  56. };
  57.  
  58. struct pline {
  59.     ld a, b, c;
  60.    
  61.     pline() {}
  62.     pline (pt p, pt q) {
  63.         a = p.y - q.y;
  64.         b = q.x - p.x;
  65.         c = - a * p.x - b * p.y;
  66.         norm();
  67.     }
  68.    
  69.     void norm() {
  70.         ld z = sqrt (a*a + b*b);
  71.         if (abs(z) > eps)
  72.             a /= z,  b /= z,  c /= z;
  73.     }
  74.    
  75.     double dist (pt p) const {
  76.         return a * p.x + b * p.y + c;
  77.     }
  78. };
  79.  
  80. #define det(a,b,c,d)  (a*d-b*c)
  81.  
  82. inline bool betw (ld l, ld r, ld x) {
  83.     return min(l,r) <= x + eps && x <= max(l,r) + eps;
  84. }
  85.  
  86. inline bool intersect_1d (ld a, ld b, ld c, ld d) {
  87.     if (a > b)  swap (a, b);
  88.     if (c > d)  swap (c, d);
  89.     return max (a, c) <= min (b, d) + eps;
  90. }
  91.  
  92. bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
  93.     if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
  94.         return false;
  95.     pline m (a, b);
  96.     pline n (c, d);
  97.     ld zn = det (m.a, m.b, n.a, n.b);
  98.     if (abs (zn) < eps) {
  99.         if (abs (m.dist (c)) > eps || abs (n.dist (a)) > eps)
  100.             return false;
  101.         if (b < a)  swap (a, b);
  102.         if (d < c)  swap (c, d);
  103.         left = max (a, c);
  104.         right = min (b, d);
  105.         return true;
  106.     }
  107.     else {
  108.         left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
  109.         left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
  110.         return betw (a.x, b.x, left.x)
  111.         && betw (a.y, b.y, left.y)
  112.         && betw (c.x, d.x, left.x)
  113.         && betw (c.y, d.y, left.y);
  114.     }
  115. }
  116.  
  117. int sign(pt a, pt b) {
  118.     ld res = a.x * b.y - a.y * b.x;
  119.     if (fabs(res) < eps) return 0;
  120.     if (res < eps) return -1;
  121.     return 1;
  122. }
  123.  
  124. ld area(pt a, pt b) {
  125.     return a.x * b.y - a.y * b.x;
  126. }
  127.  
  128. pt v[111];
  129.  
  130. pt A, B;
  131.  
  132. ld area(pt p) {
  133.     ld res = 0.0L;
  134.     for (int i = 1; i <= n; i++) {
  135.         A = v[i] - p;
  136.         B = v[i + 1] - p;
  137.         res += area(A, B);
  138.     }
  139.     return fabs(0.5L * res);
  140. }
  141.  
  142. struct point
  143. {
  144.     double x, y;
  145.     point()
  146.     {
  147.         x = y = 0;
  148.     }
  149.     point(double a, double b)
  150.     {
  151.         x = a;
  152.         y = b;
  153.     }
  154.     friend bool operator == (point a, point b)
  155.     {
  156.         if (a.x == b.x && a.y == b.y)
  157.             return true;
  158.         return false;
  159.     }
  160.     friend bool operator < (point a, point b)
  161.     {
  162.         if (a.x < b.x)
  163.             return true;
  164.         if (a.x == b.x && a.y < b.y)
  165.             return true;
  166.         return false;
  167.     }
  168.     friend bool operator > (point a, point b)
  169.     {
  170.         if (a.x > b.x)
  171.             return true;
  172.         if (a.x == b.x && a.y > b.y)
  173.             return true;
  174.         return false;
  175.     }
  176. };
  177.  
  178. struct line
  179. {
  180.     double a, b, c;
  181.     line()
  182.     {
  183.         a = b = c = 0;
  184.     }
  185.     line(double z, double x, double y)
  186.     {
  187.         a = z;
  188.         b = x;
  189.         c = y;
  190.     }
  191. };
  192.  
  193. double DotProduct(point a, point b)
  194. {
  195.     return a.x*b.x + a.y*b.y;
  196. }
  197.  
  198. double CrossProduct(point a, point b)
  199. {
  200.     return a.x*b.y - b.x*a.y;
  201. }
  202.  
  203. double angle(point a, point b)
  204. {
  205.     return atan2(CrossProduct(a, b), DotProduct(a, b));
  206. }
  207.  
  208. line makeLine(point a, point b)
  209. {
  210.     return line(b.y - a.y, a.x - b.x, (a.y - b.y)*a.x + (b.x - a.x)*a.y);
  211. }
  212.  
  213. point LinesCross(line a, line b)
  214. {
  215.     double y = (b.a*a.c - a.a*b.c) / (a.a*b.b - b.a*a.b);
  216.     if (y == -0)
  217.         y = 0;
  218.     return point((-1)*(a.c + a.b*y) / a.a, y);
  219. }
  220.  
  221. double lenght(point a, point b)
  222. {
  223.     return sqrt(pow((b.x - a.x), 2) + pow((b.y - a.y), 2));
  224. }
  225.  
  226. pt start;
  227. double lenghtToPoint(line v, point a)
  228. {
  229.     return abs((v.a*a.x + v.b*a.y + v.c) / sqrt(v.a*v.a + v.b*v.b));
  230. }
  231.  
  232. pt move;
  233.  
  234.  
  235. ld bestDist;
  236. pt gg, l_point, r_point, le, ri, suck;
  237.  
  238. pt getNearest(pt p) {
  239.     l_point = p;
  240.     r_point = p + move;
  241.     pt res(INF, INF);
  242.     bestDist = INF;
  243.     for (int i = 1; i <= n; i++) {
  244.         if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
  245.             suck = ri - le;
  246.             if (suck.getLen() > eps) {
  247.                 continue;
  248.             }
  249.             suck = p - le;
  250.             if (suck.getLen() < bestDist) {
  251.                 bestDist = suck.getLen();
  252.                 res = le;
  253.             }
  254.         }
  255.     }
  256.     return res;
  257. }
  258.  
  259.  
  260.  
  261. vector< pair<ld, pt> > have;
  262. point p[333];
  263.  
  264. bool contains(pt tt) {
  265.     ////awdawdaw
  266.    
  267.     ld ang = 0.0;
  268.     point t = point(tt.x, tt.y);
  269.     for (int i = 1; i <= n; i++)
  270.     {
  271.         if (p[i] == t || p[i + 1] == t)
  272.         {
  273.             return true;
  274.         }
  275.         double ang1 = abs(angle(point(p[i].x - t.x, p[i].y - t.y), point(p[i + 1].x - t.x, p[i + 1].y - t.y)));
  276.         if (CrossProduct(point(p[i].x - t.x, p[i].y - t.y), point(p[i + 1].x - t.x, p[i + 1].y - t.y)) <= 0)
  277.             ang += ang1;
  278.         else ang -= ang1;
  279.     }
  280.     if (abs(ang) < eps) return false;
  281.     else return true;
  282.    
  283.    
  284.    
  285.    
  286.    
  287. }
  288.  
  289. bool cmp(pair<ld, pt> a, pair<ld, pt> b) {
  290.     if (fabs(a.F - b.F) <= eps) return a < b;
  291.     return a.F + eps < b.F;
  292. }
  293.  
  294. void addHave(pt p) {
  295.     pt delta = p - start;
  296.     have.pb(mp(delta.getLen(), p));
  297. }
  298.  
  299. void solve(pt l_point, pt r_point) {
  300.     pt le, ri;
  301.     for (int i = 1; i <= n; i++) {
  302.         if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
  303.             suck = ri - le;
  304.             if (suck.getLen() > eps) {
  305.                 addHave(le);
  306.                 addHave(ri);
  307.             } else addHave(le);
  308.         }
  309.     }
  310.     sort(have.begin(), have.end(), cmp);
  311.     vector< pair<ld, pt> > dick;
  312.     dick.pb(have[0]);
  313.     for (int i = 1; i < (int)have.size(); i++) {
  314.         pt ra = have[i].S - dick.back().S;
  315.         if (ra.getLen() <= eps) continue;
  316.         dick.pb(have[i]);
  317.     }
  318.     dick.swap(have);
  319. }
  320.  
  321. bool dont(pt l_point, pt r_point) {
  322.     pt le, ri;
  323.     for (int i = 1; i <= n; i++) {
  324.         if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
  325.             le = le - l_point;
  326.             ri = ri - r_point;
  327.             if (le.getLen() <= eps && ri.getLen() <= eps) return false;
  328.         }
  329.     }
  330.     return true;
  331. }
  332.  
  333. int main() {
  334.     scanf("%d", &n);
  335.     for (int i = 1; i <= n; i++) {
  336.         double x, y;
  337.         cin >> x >> y;
  338.         v[i] = pt(1.0L * x, 1.0L * y);
  339.     }
  340.     v[n + 1] = v[1];
  341.     for (int i = 1; i <= n + 1; i++) p[i] = point(v[i].x, v[i].y);
  342.     cin >> start.x >> start.y;
  343.     cin >> move.x >> move.y;
  344.     move = move.mult(1e9L);
  345.     have.pb(mp(0.0L, start));
  346.     ld ans = 0.0L;
  347.     solve(start, start + move);
  348.    // for (int i = 0; i < have.size(); i++) {
  349.   //      cout << have[i].S.x << " " << have[i].S.y << "!" << endl;
  350.    // }
  351.     //return 0;
  352.     if ((int)have.size() == 0) {
  353.         puts("0.00000000000");
  354.         return 0;
  355.     }
  356.     pt p1, p2, p3;
  357.     p1 = have[0].S + have[1].S;
  358.     p2 = p1.mult(0.5L);
  359.     bool in = contains(p2);
  360.     for (int i = 0; i + 1 < (int)have.size(); i++) {
  361.         p1 = have[i].S + have[i + 1].S;
  362.         p2 = p1.mult(0.5L);
  363.         p3 = have[i + 1].S - have[i].S;
  364.         if (contains(p2) && dont(have[i].S, have[i + 1].S)) ans += p3.getLen();
  365.     }
  366.     cout << fixed << setprecision(20) << ans << endl;
  367.     return 0;
  368. }
Advertisement
Add Comment
Please, Sign In to add comment