oj.uz

Submission #230823

# Submission time Handle Problem Language Result Execution time Memory
230823 2020-05-11T21:33:51 Z walnutwaldo20 Relay (COI16_relay) C++14
100 / 100
 137 ms 13152 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

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 % (int)v.size() + (int)v.size()) % (int)v.size()];
}

bool inside(point p, vector<point>& hull) {
    F0R(i, hull.size()) {
        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, hull.size()) {
        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, hull.size()) 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) % (int)hull.size() + (int)hull.size()) % (int)hull.size();
                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, v.size()) {
        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, v.size()) {
        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 6 ms 512 KB Output is correct
9 Correct 5 ms 512 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 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 9 ms 768 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 9 ms 512 KB Output is correct
20 Correct 8 ms 512 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 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 95 ms 4712 KB Output is correct
12 Correct 97 ms 6752 KB Output is correct
13 Correct 105 ms 6752 KB Output is correct
14 Correct 94 ms 6748 KB Output is correct
15 Correct 98 ms 6620 KB Output is correct
16 Correct 99 ms 6124 KB Output is correct
17 Correct 107 ms 7008 KB Output is correct
18 Correct 110 ms 7904 KB Output is correct
19 Correct 100 ms 6124 KB Output is correct
20 Correct 97 ms 6368 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 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 9 ms 768 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 9 ms 512 KB Output is correct
20 Correct 8 ms 512 KB Output is correct
21 Correct 95 ms 4712 KB Output is correct
22 Correct 97 ms 6752 KB Output is correct
23 Correct 105 ms 6752 KB Output is correct
24 Correct 94 ms 6748 KB Output is correct
25 Correct 98 ms 6620 KB Output is correct
26 Correct 99 ms 6124 KB Output is correct
27 Correct 107 ms 7008 KB Output is correct
28 Correct 110 ms 7904 KB Output is correct
29 Correct 100 ms 6124 KB Output is correct
30 Correct 97 ms 6368 KB Output is correct
31 Correct 137 ms 13152 KB Output is correct
32 Correct 133 ms 13028 KB Output is correct
33 Correct 127 ms 12556 KB Output is correct
34 Correct 129 ms 12516 KB Output is correct
35 Correct 114 ms 10204 KB Output is correct
36 Correct 121 ms 10208 KB Output is correct
37 Correct 127 ms 10848 KB Output is correct
38 Correct 128 ms 11232 KB Output is correct
39 Correct 107 ms 9824 KB Output is correct
40 Correct 107 ms 9956 KB Output is correct