답안 #55176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55176 2018-07-06T08:47:27 Z paulica Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
100 ms 8960 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 = 1e5 + 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);
}

void printLine(int i) {cout << line[i].fi + 1 << "-" << line[i].se + 1 << " ";}
/*
ld intersec(int i, int j) {
    int a = line[j].fi, b = line[j].se;

    if (x[a] == x[b]) return x[a];

    ld k1 = (ld)y[i] / x[i];
    ld k2 = (ld)(y[a] - y[b]) / (x[a] - x[b]);
    ld l = (ld)((ll)x[a] * y[b] - (ll)x[b] * y[a]) / (x[a] - x[b]);

    if (k1 - k2 == 0) return min(x[a], x[b]);

    *
    cout << "intersec " << i + 1 << " ";
    printLine(j);
    cout << l / (k1 -k2) << endl;

    
    return l / (k1 - k2);
}*/

bool above(int i, int j) {
    int a = line[j].fi, b = line[j].se;
    bool ret = false;
    //cout << x[a] << "," << y[a] << " " << x[b] << "," << y[b] << " " << x[i] << "," << y[i] << " " << ccw(a, b, 0) << endl; 
    if (ccw0(a, b) == 0) ret = x[i] >= max(x[a], x[b]);
    else if (i == a || i == b) ret = false;
    else ret = (ccw0(a, i) < 0) || (ccw(a, b, i) < 0) || (ccw0(i, b) < 0);
    //cout << "above " << i + 1 << " ", printLine(j), cout << " " << ret << endl;
    return ret;
}

int mod(int i) {
    if (i >= n) return i - n;
    return i;
}

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

        bool ret = false;

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

        int ty = 0;
        /* else*/ if (pointCmp(a1, a2) && pointCmp(a2, b1))
            ret = above(a2, i), ty = 1;
        else if (pointCmp(a1, b2) && pointCmp(b2, b1))
            ret = above(b2, i), ty = 2;
        else if (pointCmp(a2, a1) && pointCmp(a1, b2))
            ret = !above(a1, j), ty = 3;
        else if (pointCmp(a2, b1) && pointCmp(b1, b2))
            ret = !above(b1, j), ty = 4;
        else if (b1 == a2)
            ret = false, ty = 5;
        else if (b2 == a1)
           ret = true, ty = 6;
        //else cout << "kurac", printLine(i), printLine(j), cout << endl;


        /*
        cout << "cmp ";
        printLine(i);
        printLine(j);
        cout << ret << " " << ty << endl;
        //cin.get();
        /**/
        return ret;
    }
};

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);
            //int l = ev.fi.se;
            //cout << "+ ";
            //printLine(l);
            //cout << endl;
        } else if (ev.se == 1) {
            int i = ev.fi.se;
//            cout << endl;
         //   TRACE(i + 1);
          //  for (int l : lines) cout << line[l].fi + 1 << "-" << line[l].se + 1  << " "; cout << endl;
            int j = *lines.begin();
      //      cout << line[j].fi + 1 << "-" << line[j].se + 1 << endl;

 //           if (intersec(i, j) >= x[i]) 
            if (!above(i, j)) sol.push_back(i);
          //  if (!above(i, j)) cout << "yes\n";
        //    cout << endl;
        } else {
   //         cout << "!" << (lines.find(ev.fi.se) != lines.end()) << "!\n";
            //if (lines.find(ev.fi.se) == lines.end()) cout << "joj ", printLine(ev.fi.se), cout << endl;
      //      cout << lines.size() << " -> ";
            lines.erase(ev.fi.se);
        //    cout << lines.size() << "  ";
            //cout << "- ";
           // printLine(ev.fi.se);
           // cout << "   " << ev.fi.se << endl;
        }
    }

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

    cout << sol.size() << "\n";
    for (int i : sol) cout << i + 1 << " ";
    
/*
    cout << "\nbrut:\n";
    for (int i = 0; i < n; i++) {
        bool ok = true;
        for (int j = 0; j < n; j++)
            if (pointCmp(line[j].fi, i) && pointCmp(i, line[j].se) && above(i, j))
                    ok = false;
        if (ok) cout << i + 1 << " ";
    }
    */

    return 0;
}

Compilation message

circuit.cpp:115:9: warning: "/*" within comment [-Wcomment]
         /**/
          
circuit.cpp: In member function 'bool lineCmp::operator()(int, int)':
circuit.cpp:93:13: warning: variable 'ty' set but not used [-Wunused-but-set-variable]
         int ty = 0;
             ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 4 ms 812 KB Output is correct
4 Correct 6 ms 952 KB Output is correct
5 Correct 18 ms 1232 KB Output is correct
6 Correct 18 ms 1232 KB Output is correct
7 Correct 37 ms 1864 KB Output is correct
8 Correct 15 ms 1864 KB Output is correct
9 Correct 14 ms 1864 KB Output is correct
10 Correct 18 ms 1864 KB Output is correct
11 Correct 21 ms 1864 KB Output is correct
12 Correct 26 ms 1864 KB Output is correct
13 Correct 59 ms 2664 KB Output is correct
14 Correct 53 ms 2788 KB Output is correct
15 Correct 64 ms 4580 KB Output is correct
16 Execution timed out 127 ms 8240 KB Time limit exceeded
17 Execution timed out 239 ms 8340 KB Time limit exceeded
18 Runtime error 27 ms 8340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 27 ms 8340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Execution timed out 193 ms 8960 KB Time limit exceeded