oj.uz

답안 #140332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140332 2019-08-02T14:48:58 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
15 / 100
 100 ms 31704 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 intersect(point a, point b, point c) {
    long long s = vec(a, c);
    long long s1 = vec(c, b);
    if (s == 0 && s1 == 0) {
        return true;
    }
    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]; 


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;
    }
    for (int i = 0; i < n; i++) {
        int j = where[i + 1];
        int k = where[(i + 1) % n + 1];
        if (j > k) {
            swap(j, k);
        }
        add[j].pb({q[i], q[(i + 1) % n]});
        del[k].pb({q[i], q[(i + 1) % n]});
    }
    vector<int> f;
    for (int i = 0; i < n; i++) {
        bool bad = false;
        if (!s.empty() && intersect(s.begin()->second.first, s.begin()->second.second, p[i])) {
            bad = true;
        }
        for (auto x: add[i]) {
            point d = x.first + x.second;
            s.insert({d, x});
        }
        if (s.empty() || !intersect(s.begin()->second.first, s.begin()->second.second, p[i])) {
            good[p[i].id] = true;
        }
        for (auto x: del[i]) {
            point d = x.first + x.second;
            s.erase({d, x});
        }
        if (!s.empty() && intersect(s.begin()->second.first, s.begin()->second.second, p[i])) {
            good[p[i].id] = false;
        }
        if (bad) {
            good[p[i].id] = false;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (good[i]) {
            f.pb(i);
        }
    }
    cout << sz(f) << '\n';
    for (auto x: f) {
        cout << x << ' ';
    }
    cout << endl;
    return 0; 
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Incorrect 11 ms 9848 KB Output isn't correct
3 Incorrect 13 ms 10108 KB Output isn't correct
4 Correct 14 ms 10232 KB Output is correct
5 Incorrect 22 ms 11000 KB Output isn't correct
6 Incorrect 21 ms 11000 KB Output isn't correct
7 Incorrect 36 ms 12272 KB Output isn't correct
8 Incorrect 19 ms 10744 KB Output isn't correct
9 Incorrect 24 ms 11000 KB Output isn't correct
10 Incorrect 21 ms 11000 KB Output isn't correct
11 Incorrect 24 ms 11128 KB Output isn't correct
12 Incorrect 27 ms 11768 KB Output isn't correct
13 Incorrect 49 ms 13176 KB Output isn't correct
14 Correct 44 ms 13748 KB Output is correct
15 Incorrect 51 ms 14456 KB Output isn't correct
16 Incorrect 93 ms 19120 KB Output isn't correct
17 Execution timed out 167 ms 20728 KB Time limit exceeded
18 Execution timed out 181 ms 28408 KB Time limit exceeded
19 Execution timed out 176 ms 28332 KB Time limit exceeded
20 Execution timed out 374 ms 31704 KB Time limit exceeded