oj.uz

Submission #230824

# Submission time Handle Problem Language Result Execution time Memory
230824 2020-05-11T21:35:49 Z walnutwaldo20 Relay (COI16_relay) C++14
100 / 100
 155 ms 9828 KB 
#include <bits/stdc++.h>

#define F0R(i, a) for (int i = 0; i < (int)(a); i++)

#define PB push_back
#define MP make_pair
#define X real()
#define Y imag()

#define F first
#define S second

#define sz(x) (int)((x).size())

using namespace std;

typedef long long ll;
typedef long double ld;

typedef complex<ld> point;
typedef pair<point, point> edge;

#define MAXN 100000

bool reaches[MAXN];

edge rev(edge e) { return MP(e.S, e.F); }

ll crossp(point p1, point p2) {
    return (conj(p1) * p2).Y;
}

ll dotp(point p1, point p2) {
    return (conj(p1) * p2).X;
}

bool rightof(point p, edge e) {
    bool ret = crossp(e.S - e.F, p - e.S) <= 0;
    return ret;
}

point get(vector<point>& v, int idx) {
    return v[(idx % sz(v) + sz(v)) % sz(v)];
}

bool inside(point p, vector<point>& hull) {
    F0R(i, sz(hull)) {
        edge e = MP(hull[i], get(hull, i + 1));
        if (rightof(p, e)) {
            return false;
        }
    }
    return true;
}

point findtangent(vector<point>&hull, point p, bool seen1, bool seen2) {
    F0R(i, sz(hull)) {
        edge edge1 = MP(get(hull, i - 1), hull[i]);
        edge edge2 = MP(hull[i], get(hull, i + 1));
        if (rightof(p, edge1) == seen1 && rightof(p, edge2) == seen2) {
            return hull[i];
        }
    }
    cout << "this should not print" << endl;
    exit(0);
}

ld cosbw(point e1, point e2) {
    ld res = dotp(e1, e2);
    res /= abs(e1);
    res /= abs(e2);
    return res;
}

edge findfarthest(vector<point>& candidates, edge tangent, int dir, vector<point>& hull) {
    int idx = 0;
    F0R(i, sz(hull)) if (hull[i] == tangent.S) {
        idx = i;
    }
    
    edge res = tangent;
    ld mincos = 1;
    for (const point p : candidates) {
        edge curr = MP(p, hull[idx]);
        while (1) {
            edge e = MP(hull[idx], get(hull, idx + dir));
            if (dir < 0) {
                e = rev(e);
            }
            if (rightof(p, e)) {
                idx = ((idx + dir) % sz(hull) + sz(hull)) % sz(hull);
                curr = MP(p, get(hull, idx));
            } else {
                break;
            }
        }
        
        ld c = cosbw(curr.S - curr.F, tangent.S - tangent.F);
        if (c < mincos) {
            res = curr;
            mincos = c;
        }
    }
    return res;
}

void read(int& len, vector<point>& vec) {
    cin >> len;
    F0R(i, len) {
        ll x, y;
        cin >> x >> y;
        vec.PB(point(x, y));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    vector<point> v, hull;
    read(n, v);
    read(m, hull);
    
    point righttangent = findtangent(hull, v[0], true, false);
    point lefttangent = findtangent(hull, v[0], false, true);
    
    vector<point> triangle;
    triangle.PB(v[0]);
    triangle.PB(righttangent);
    triangle.PB(lefttangent);
    
    vector<point> leftpoints, rightpoints;
    F0R(i, sz(v)) {
        if (inside(v[i], triangle)) {
            reaches[i] = true;
        }
        if (rightof(v[i], MP(v[0], righttangent))) {
            reaches[i] = true;
            rightpoints.PB(v[i]);
        }
        if (rightof(v[i], MP(lefttangent, v[0]))) {
            reaches[i] = true;
            leftpoints.PB(v[i]);
        }
    }
    
    edge farthestleft = findfarthest(leftpoints, MP(v[0], lefttangent), -1, hull);
    edge farthestright = findfarthest(rightpoints, MP(v[0], righttangent), 1, hull);
    
    vector<point> lefttriangle;
    lefttriangle.PB(farthestleft.F);
    lefttriangle.PB(lefttangent);
    lefttriangle.PB(farthestleft.S);
    
    vector<point> righttriangle;
    righttriangle.PB(farthestright.F);
    righttriangle.PB(farthestright.S);
    righttriangle.PB(righttangent);
    
    F0R(i, sz(v)) {
        if (rightof(v[i], rev(farthestleft))) {
            reaches[i] = true;
        }
        if (rightof(v[i], farthestright)) {
            reaches[i] = true;
        }
        if (inside(v[i], lefttriangle)) {
            reaches[i] = true;
        }
        if (inside(v[i], righttriangle)) {
            reaches[i] = true;
        }
    }
    int res = 0;
    F0R(i, n) if (reaches[i]) {
        res++;
    }
    cout << res - 1 << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 512 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 8 ms 512 KB Output is correct
16 Correct 8 ms 640 KB Output is correct
17 Correct 8 ms 512 KB Output is correct
18 Correct 8 ms 512 KB Output is correct
19 Correct 8 ms 512 KB Output is correct
20 Correct 8 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 102 ms 4704 KB Output is correct
12 Correct 93 ms 4836 KB Output is correct
13 Correct 94 ms 4844 KB Output is correct
14 Correct 91 ms 4832 KB Output is correct
15 Correct 93 ms 4724 KB Output is correct
16 Correct 89 ms 4724 KB Output is correct
17 Correct 96 ms 5088 KB Output is correct
18 Correct 98 ms 5988 KB Output is correct
19 Correct 97 ms 4596 KB Output is correct
20 Correct 91 ms 4724 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 512 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 8 ms 512 KB Output is correct
16 Correct 8 ms 640 KB Output is correct
17 Correct 8 ms 512 KB Output is correct
18 Correct 8 ms 512 KB Output is correct
19 Correct 8 ms 512 KB Output is correct
20 Correct 8 ms 640 KB Output is correct
21 Correct 102 ms 4704 KB Output is correct
22 Correct 93 ms 4836 KB Output is correct
23 Correct 94 ms 4844 KB Output is correct
24 Correct 91 ms 4832 KB Output is correct
25 Correct 93 ms 4724 KB Output is correct
26 Correct 89 ms 4724 KB Output is correct
27 Correct 96 ms 5088 KB Output is correct
28 Correct 98 ms 5988 KB Output is correct
29 Correct 97 ms 4596 KB Output is correct
30 Correct 91 ms 4724 KB Output is correct
31 Correct 133 ms 9828 KB Output is correct
32 Correct 155 ms 9752 KB Output is correct
33 Correct 124 ms 9568 KB Output is correct
34 Correct 119 ms 9752 KB Output is correct
35 Correct 114 ms 7268 KB Output is correct
36 Correct 117 ms 7272 KB Output is correct
37 Correct 121 ms 7904 KB Output is correct
38 Correct 126 ms 8448 KB Output is correct
39 Correct 110 ms 7104 KB Output is correct
40 Correct 105 ms 7012 KB Output is correct