Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <cstdlib>
- #include <utility>
- #include <memory.h>
- #include <iterator>
- #include <iomanip>
- #include <queue>
- #include <ctime>
- #include <deque>
- #include <set>
- #include <map>
- #define move mov_e
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- typedef long double ld;
- const ld eps = 1e-7L;
- const ld INF = 1e9L;
- int n;
- struct pt {
- ld x, y;
- pt () {};
- pt (ld x, ld y) {
- this -> x = x;
- this -> y = y;
- }
- pt operator - (const pt &p) {
- return pt(x - p.x, y - p.y);
- }
- pt mult(ld C) {
- return pt(x * C, y * C);
- }
- pt operator + (const pt &p) {
- return pt(x + p.x, y + p.y);
- }
- ld getLen() {
- return sqrt(x * x + y * y);
- }
- bool operator< (const pt & p) const {
- return (x < p.x-eps) || (abs(x-p.x) < eps && y < p.y - eps);
- }
- };
- struct pline {
- ld a, b, c;
- pline() {}
- pline (pt p, pt q) {
- a = p.y - q.y;
- b = q.x - p.x;
- c = - a * p.x - b * p.y;
- norm();
- }
- void norm() {
- ld z = sqrt (a*a + b*b);
- if (abs(z) > eps)
- a /= z, b /= z, c /= z;
- }
- double dist (pt p) const {
- return a * p.x + b * p.y + c;
- }
- };
- #define det(a,b,c,d) (a*d-b*c)
- inline bool betw (ld l, ld r, ld x) {
- return min(l,r) <= x + eps && x <= max(l,r) + eps;
- }
- inline bool intersect_1d (ld a, ld b, ld c, ld d) {
- if (a > b) swap (a, b);
- if (c > d) swap (c, d);
- return max (a, c) <= min (b, d) + eps;
- }
- bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
- if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
- return false;
- pline m (a, b);
- pline n (c, d);
- ld zn = det (m.a, m.b, n.a, n.b);
- if (abs (zn) < eps) {
- if (abs (m.dist (c)) > eps || abs (n.dist (a)) > eps)
- return false;
- if (b < a) swap (a, b);
- if (d < c) swap (c, d);
- left = max (a, c);
- right = min (b, d);
- return true;
- }
- else {
- left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
- left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
- return betw (a.x, b.x, left.x)
- && betw (a.y, b.y, left.y)
- && betw (c.x, d.x, left.x)
- && betw (c.y, d.y, left.y);
- }
- }
- int sign(pt a, pt b) {
- ld res = a.x * b.y - a.y * b.x;
- if (fabs(res) < eps) return 0;
- if (res < eps) return -1;
- return 1;
- }
- ld area(pt a, pt b) {
- return a.x * b.y - a.y * b.x;
- }
- pt v[111];
- pt A, B;
- ld area(pt p) {
- ld res = 0.0L;
- for (int i = 1; i <= n; i++) {
- A = v[i] - p;
- B = v[i + 1] - p;
- res += area(A, B);
- }
- return fabs(0.5L * res);
- }
- struct point
- {
- double x, y;
- point()
- {
- x = y = 0;
- }
- point(double a, double b)
- {
- x = a;
- y = b;
- }
- friend bool operator == (point a, point b)
- {
- if (a.x == b.x && a.y == b.y)
- return true;
- return false;
- }
- friend bool operator < (point a, point b)
- {
- if (a.x < b.x)
- return true;
- if (a.x == b.x && a.y < b.y)
- return true;
- return false;
- }
- friend bool operator > (point a, point b)
- {
- if (a.x > b.x)
- return true;
- if (a.x == b.x && a.y > b.y)
- return true;
- return false;
- }
- };
- struct line
- {
- double a, b, c;
- line()
- {
- a = b = c = 0;
- }
- line(double z, double x, double y)
- {
- a = z;
- b = x;
- c = y;
- }
- };
- double DotProduct(point a, point b)
- {
- return a.x*b.x + a.y*b.y;
- }
- double CrossProduct(point a, point b)
- {
- return a.x*b.y - b.x*a.y;
- }
- double angle(point a, point b)
- {
- return atan2(CrossProduct(a, b), DotProduct(a, b));
- }
- line makeLine(point a, point b)
- {
- return line(b.y - a.y, a.x - b.x, (a.y - b.y)*a.x + (b.x - a.x)*a.y);
- }
- point LinesCross(line a, line b)
- {
- double y = (b.a*a.c - a.a*b.c) / (a.a*b.b - b.a*a.b);
- if (y == -0)
- y = 0;
- return point((-1)*(a.c + a.b*y) / a.a, y);
- }
- double lenght(point a, point b)
- {
- return sqrt(pow((b.x - a.x), 2) + pow((b.y - a.y), 2));
- }
- pt start;
- double lenghtToPoint(line v, point a)
- {
- return abs((v.a*a.x + v.b*a.y + v.c) / sqrt(v.a*v.a + v.b*v.b));
- }
- pt move;
- ld bestDist;
- pt gg, l_point, r_point, le, ri, suck;
- pt getNearest(pt p) {
- l_point = p;
- r_point = p + move;
- pt res(INF, INF);
- bestDist = INF;
- for (int i = 1; i <= n; i++) {
- if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
- suck = ri - le;
- if (suck.getLen() > eps) {
- continue;
- }
- suck = p - le;
- if (suck.getLen() < bestDist) {
- bestDist = suck.getLen();
- res = le;
- }
- }
- }
- return res;
- }
- vector< pair<ld, pt> > have;
- point p[333];
- bool contains(pt tt) {
- ////awdawdaw
- ld ang = 0.0;
- point t = point(tt.x, tt.y);
- for (int i = 1; i <= n; i++)
- {
- if (p[i] == t || p[i + 1] == t)
- {
- return true;
- }
- 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)));
- 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)
- ang += ang1;
- else ang -= ang1;
- }
- if (abs(ang) < eps) return false;
- else return true;
- }
- bool cmp(pair<ld, pt> a, pair<ld, pt> b) {
- if (fabs(a.F - b.F) <= eps) return a < b;
- return a.F + eps < b.F;
- }
- void addHave(pt p) {
- pt delta = p - start;
- have.pb(mp(delta.getLen(), p));
- }
- void solve(pt l_point, pt r_point) {
- pt le, ri;
- for (int i = 1; i <= n; i++) {
- if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
- suck = ri - le;
- if (suck.getLen() > eps) {
- addHave(le);
- addHave(ri);
- } else addHave(le);
- }
- }
- sort(have.begin(), have.end(), cmp);
- vector< pair<ld, pt> > dick;
- dick.pb(have[0]);
- for (int i = 1; i < (int)have.size(); i++) {
- pt ra = have[i].S - dick.back().S;
- if (ra.getLen() <= eps) continue;
- dick.pb(have[i]);
- }
- dick.swap(have);
- }
- bool dont(pt l_point, pt r_point) {
- pt le, ri;
- for (int i = 1; i <= n; i++) {
- if (intersect(v[i], v[i + 1], l_point, r_point, le, ri)) {
- le = le - l_point;
- ri = ri - r_point;
- if (le.getLen() <= eps && ri.getLen() <= eps) return false;
- }
- }
- return true;
- }
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- double x, y;
- cin >> x >> y;
- v[i] = pt(1.0L * x, 1.0L * y);
- }
- v[n + 1] = v[1];
- for (int i = 1; i <= n + 1; i++) p[i] = point(v[i].x, v[i].y);
- cin >> start.x >> start.y;
- cin >> move.x >> move.y;
- move = move.mult(1e9L);
- have.pb(mp(0.0L, start));
- ld ans = 0.0L;
- solve(start, start + move);
- // for (int i = 0; i < have.size(); i++) {
- // cout << have[i].S.x << " " << have[i].S.y << "!" << endl;
- // }
- //return 0;
- if ((int)have.size() == 0) {
- puts("0.00000000000");
- return 0;
- }
- pt p1, p2, p3;
- p1 = have[0].S + have[1].S;
- p2 = p1.mult(0.5L);
- bool in = contains(p2);
- for (int i = 0; i + 1 < (int)have.size(); i++) {
- p1 = have[i].S + have[i + 1].S;
- p2 = p1.mult(0.5L);
- p3 = have[i + 1].S - have[i].S;
- if (contains(p2) && dont(have[i].S, have[i + 1].S)) ans += p3.getLen();
- }
- cout << fixed << setprecision(20) << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment