oj.uz

Submission #140296

# Submission time Handle Problem Language Result Execution time Memory
140296 2019-08-02T13:44:47 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 88 ms 5620 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 a.x * b.y - 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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 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 4 ms 504 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 10 ms 760 KB Output isn't correct
8 Incorrect 5 ms 632 KB Output isn't correct
9 Incorrect 4 ms 504 KB Output isn't correct
10 Incorrect 7 ms 632 KB Output isn't correct
11 Incorrect 6 ms 632 KB Output isn't correct
12 Incorrect 8 ms 760 KB Output isn't correct
13 Incorrect 14 ms 1144 KB Output isn't correct
14 Incorrect 17 ms 1016 KB Output isn't correct
15 Incorrect 19 ms 1016 KB Output isn't correct
16 Incorrect 36 ms 1784 KB Output isn't correct
17 Incorrect 43 ms 2168 KB Output isn't correct
18 Incorrect 73 ms 4716 KB Output isn't correct
19 Incorrect 81 ms 5620 KB Output isn't correct
20 Incorrect 88 ms 4984 KB Output isn't correct