답안 #55183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55183 2018-07-06T08:53:45 Z paulica Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
100 ms 16012 KB
#include <bits/stdc++.h>
using namespace std;

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int MaxN = 2e5 + 10;

int n, x[MaxN], y[MaxN];
pair<int, int> line[MaxN];

ll ccw(int i, int j, int k) {
    return (ll)x[i] * (y[j] - y[k]) +
           (ll)x[j] * (y[k] - y[i]) +
           (ll)x[k] * (y[i] - y[j]);
}

ll ccw0(int i, int j) {
    return (ll)x[i] * y[j] - (ll)x[j] * y[i];
}

ll dist(int i) {
    return (ll)x[i] * x[i] + (ll)y[i] * y[i];
}

bool equ(int i, int j) {
    return (ll)y[i] * x[j] == (ll)y[j] * x[i];
}

bool pointCmp(int i, int j) {
    if (equ(i, j)) return dist(i) < dist(j);
    return (ll)y[i] * x[j] < (ll)y[j] * x[i];
}

bool eventCmp(pair<pii, int>& a, pair<pii, int>& b) {
    if (equ(a.fi.fi, b.fi.fi) && a.se != b.se) return a.se < b.se;
    return pointCmp(a.fi.fi, b.fi.fi);
}

bool above(int i, int j) {
    int a = line[j].fi, b = line[j].se;

    if (ccw0(a, b) == 0) return x[i] >= max(x[a], x[b]);
    else if (i == a || i == b) return false;
    else return (ccw0(a, i) < 0) || (ccw(a, b, i) < 0) || (ccw0(i, b) < 0);
}

struct lineCmp {
    bool operator()(int i, int j) {
        if (i == j) return false;

        int a1 = line[i].fi, b1 = line[i].se;
        int a2 = line[j].fi, b2 = line[j].se;

        if (pointCmp(a1, a2) && pointCmp(a2, b1))
            return above(a2, i);
        else if (pointCmp(a1, b2) && pointCmp(b2, b1))
            return above(b2, i);
        else if (pointCmp(a2, a1) && pointCmp(a1, b2))
            return !above(a1, j);
        else if (pointCmp(a2, b1) && pointCmp(b1, b2))
            return !above(b1, j);
        else if (b1 == a2)
            return false;
        else if (b2 == a1)
           return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    vector<pair<pii, int>> events;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        events.push_back({{i, i}, 1});
    }
    
    for (int i = 0; i < n; i++) {
        if (i == n - 1) line[i] = {i, 0};
        else line[i] = {i, i + 1};
        
        if (pointCmp(line[i].se, line[i].fi))
            swap(line[i].fi, line[i].se);

        events.push_back({{line[i].fi, i}, 0});
        events.push_back({{line[i].se, i}, 2});
    }

    sort(events.begin(), events.end(), eventCmp);

    multiset<int, lineCmp> lines;

    vector<int> sol;

    for (auto ev : events) {
        if (ev.se == 0) {
            lines.insert(ev.fi.se);
        } else if (ev.se == 1) {
            int i = ev.fi.se;
            int j = *lines.begin();
            if (!above(i, j)) sol.push_back(i);
        } else {
            lines.erase(ev.fi.se);
        }
    }

    sort(sol.begin(), sol.end());

    cout << sol.size() << "\n";
    for (int i : sol) cout << i + 1 << " ";

    return 0;
}

Compilation message

circuit.cpp: In member function 'bool lineCmp::operator()(int, int)':
circuit.cpp:73:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 5 ms 756 KB Output is correct
4 Correct 6 ms 948 KB Output is correct
5 Correct 18 ms 1156 KB Output is correct
6 Correct 18 ms 1188 KB Output is correct
7 Correct 41 ms 1708 KB Output is correct
8 Correct 15 ms 1708 KB Output is correct
9 Correct 23 ms 1708 KB Output is correct
10 Correct 19 ms 1708 KB Output is correct
11 Correct 24 ms 1708 KB Output is correct
12 Correct 31 ms 1800 KB Output is correct
13 Correct 78 ms 2696 KB Output is correct
14 Correct 84 ms 2812 KB Output is correct
15 Correct 91 ms 4604 KB Output is correct
16 Execution timed out 134 ms 8308 KB Time limit exceeded
17 Execution timed out 288 ms 8308 KB Time limit exceeded
18 Execution timed out 325 ms 16012 KB Time limit exceeded
19 Execution timed out 321 ms 16012 KB Time limit exceeded
20 Execution timed out 786 ms 16012 KB Time limit exceeded