oj.uz

답안 #140309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140309 2019-08-02T13:58:43 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 89 ms 5412 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;
}


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


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


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;
    }
    g = point(1e9, 1e9);
    for (int i = 0; i < n; i++) {
        if (g.y > p[i].y) {
            g = p[i];
        } else if (g.y == p[i].y) {
            if (g.x > p[i].x) {
                g = p[i];
            }
        }
    }
    sort(p, p + n, comp);
    int m = n;
    vector<int> st;
    for (int i = 0; i < n; i++) {
        if (sz(st) < 2) {
            st.pb(i);
        } else {    
            while (sz(st) >= 2 && vec(p[st.back()] - p[st[sz(st) - 2]], p[i] - p[st[sz(st) - 2]]) <= 0) {
                st.pop_back();
            }
            st.pb(i);
        }
    }
    while (sz(st) >= 2 && vec(p[st.back()] - p[st[sz(st) - 2]], p[0] - p[st[sz(st) - 2]]) <= 0) {
        st.pop_back();
    }
    for (int i = 0; i < sz(st); i++) {
        q[i] = p[st[i]];
    }
    n = sz(st);
    int uk = 0;
    int uk1 = 0;
    good[q[uk].id] = true;
    int cnt = 0;
    while (vec(q[uk], q[(uk + 1) % n]) < 0) {
        uk++;
        uk %= n;
          good[q[uk].id] = true;
        cnt++;
        if (cnt >= n) {
            break;
        }
    }
    cnt = 0;
    while (vec(q[uk1], q[(uk1 - 1 + n) % n]) > 0) {
        uk1 = (uk1 - 1 + n) % n;
        good[q[uk1].id] = true;
         cnt++;
        if (cnt >= n) {
            break;
        }
    }
    vector<int> f;
    for (int i = 1; i <= m; i++) {
        if (good[i]) {
            f.pb(i);
        }
    }
    cout << sz(f) << '\n';
    for (auto x: f) {
        cout << x << ' ';
    }
    cout << endl;
    return 0; 
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Incorrect 1 ms 376 KB Output isn't correct
5 Incorrect 6 ms 632 KB Output isn't correct
6 Incorrect 6 ms 632 KB Output isn't correct
7 Incorrect 11 ms 888 KB Output isn't correct
8 Incorrect 5 ms 504 KB Output isn't correct
9 Incorrect 5 ms 504 KB Output isn't correct
10 Incorrect 6 ms 632 KB Output isn't correct
11 Incorrect 6 ms 632 KB Output isn't correct
12 Incorrect 9 ms 760 KB Output isn't correct
13 Incorrect 15 ms 1136 KB Output isn't correct
14 Incorrect 15 ms 1292 KB Output isn't correct
15 Incorrect 19 ms 1528 KB Output isn't correct
16 Incorrect 39 ms 2808 KB Output isn't correct
17 Incorrect 45 ms 2936 KB Output isn't correct
18 Incorrect 75 ms 5244 KB Output isn't correct
19 Incorrect 74 ms 5240 KB Output isn't correct
20 Incorrect 89 ms 5412 KB Output isn't correct