Submission #140370

# Submission time Handle Problem Language Result Execution time Memory
140370 2019-08-02T16:24:55 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
75 / 100
100 ms 31072 KB
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { x = (x > y ? y: x);}
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { x = (x < y ? y: x);}
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 200228;


struct point
{
    int x, y;
    int id;
    point(){}
    point(int _x, int _y) {
        x = _x;
        y = _y;
    }
};


bool good[MAXN];


point operator +(const point &a, const point &b) {
    return point(a.x + b.x, a.y + b.y);
}


point operator -(const point &a, const point &b) {
    return point(a.x - b.x, a.y - b.y);
}


long long dist(const point &a, const point &b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}


long long vec(const point &a, const point &b) {
    return 1LL * a.x * b.y - 1LL * a.y * b.x;
}


bool operator <(const point &a, const point &b) {
    return dist(a, point(0, 0)) < dist(b, point(0, 0));
}

int n;
point p[MAXN];
point g;


bool comp(const point &a, const point &b) {
    long long s = vec(a, b);
    if (s == 0) {
        return dist(a, point(0, 0)) < dist(b, point(0, 0));
    }
    return s > 0;
}


bool operator ==(const point &a, const point &b) {
    return a.x == b.x && a.y == b.y;
}


bool intersect(point a, point b, point c) {
    if (c == a || c == b) {
        return false;
    }
    long long s = vec(a, c);
    long long s1 = vec(c, b);
    if (s == 0) {
        return dist(point(0, 0), a) < dist(point(0, 0), c);
    }
    if (s1 == 0) {
        return dist(point(0, 0), b) < dist(point(0, 0), c);
    }
    if (s > 0 && s1 < 0) {
        return false;
    }
    if (s < 0 && s1 > 0) {
        return false;
    }
    s = vec(c - a, b - a);
    s1 = vec(b - a, point(0, 0) - a);
    if (s > 0 && s1 < 0) {
        return false;
    }
    if (s < 0 && s1 > 0) {
        return false;
    }
    return true;
}



set<pair<point, pair<point, point> > >  s;
point q[MAXN];
int where[MAXN];
vector<pair<point, point> >add[MAXN], del[MAXN]; 
bool bads[MAXN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME); 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
        p[i].id = i + 1;
        q[i] = p[i];
    }
    sort(p, p + n, comp);
    for (int i = 0; i < n; i++) {
        where[p[i].id] = i;
        if (i + 1 < n && vec(p[i], p[(i + 1) % n]) == 0) {
            bads[p[(i + 1) % n].id] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        int j = where[i + 1];
        int k = where[(i + 1) % n + 1];
        point a = q[i];
        point b = q[(i + 1) % n];
        if (j > k) {
            swap(j, k);
            swap(a, b);
        }
        add[j].pb({a, b});
        del[k].pb({a, b});
    }
    vector<int> f;
    for (int i = 0; i < n; i++) {
        bool bad = false;
        int cnt = 0;
        for (auto x: s) {
            if (intersect(x.second.first, x.second.second, p[i])) {
                bad = true;
                break;
            }
            cnt++;
            // if (cnt >= 10) {
            //     break;
            // }
        }
        
        for (auto x: add[i]) {
            point d = x.first + x.second;
            s.insert({d, x});
        }
        cnt = 0;
         for (auto x: s) {
            if (intersect(x.second.first, x.second.second, p[i])) {
                bad = true;
                break;
            }
            cnt++;
            // if (cnt >= 10) {
            //     break;
            // }
        }
        for (auto x: del[i]) {
            point d = x.first + x.second;
            s.erase({d, x});
        }
         cnt = 0;
         for (auto x: s) {
            if (intersect(x.second.first, x.second.second, p[i])) {
                bad = true;
                break;
            }
            cnt++;
            // if (cnt >= 10) {
            //     break;
            // }
        }
        if (!bad) {
            good[p[i].id] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (good[i] && !bads[i]) {
            f.pb(i);
        }
    }
    cout << sz(f) << '\n';
    for (auto x: f) {
        cout << x << ' ';
    }
    cout << endl;
    return 0; 
}


# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9848 KB Output is correct
3 Correct 13 ms 10104 KB Output is correct
4 Correct 14 ms 10232 KB Output is correct
5 Correct 22 ms 10872 KB Output is correct
6 Correct 21 ms 10872 KB Output is correct
7 Correct 37 ms 11896 KB Output is correct
8 Correct 20 ms 10616 KB Output is correct
9 Execution timed out 834 ms 11100 KB Time limit exceeded
10 Correct 23 ms 10872 KB Output is correct
11 Correct 24 ms 11000 KB Output is correct
12 Correct 26 ms 11640 KB Output is correct
13 Correct 59 ms 13052 KB Output is correct
14 Correct 44 ms 13432 KB Output is correct
15 Correct 52 ms 14328 KB Output is correct
16 Correct 100 ms 18936 KB Output is correct
17 Execution timed out 191 ms 20476 KB Time limit exceeded
18 Execution timed out 182 ms 27896 KB Time limit exceeded
19 Execution timed out 179 ms 27868 KB Time limit exceeded
20 Execution timed out 416 ms 31072 KB Time limit exceeded