oj.uz

Submission #140288

# Submission time Handle Problem Language Result Execution time Memory
140288 2019-08-02T13:21:31 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 43 ms 4344 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 = 100228;


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


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);
    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;
    while (vec(q[uk], q[(uk + 1) % n]) < 0) {
        uk++;
    }
    while (vec(q[uk1], q[(uk1 - 1 + n) % n]) > 0) {
        uk1 = (uk1 - 1 + n) % n;
    }
    cout << uk + 1 + n - uk1 << endl;
    for (int i = 0; i <= uk; i++) {
        cout << q[i].id << ' ';
    }
    for (int i = uk1; i < n; i++) {
        cout << q[i].id << ' ';
    }
    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 380 KB Output isn't correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Incorrect 4 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 10 ms 888 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 6 ms 632 KB Output isn't correct
11 Incorrect 9 ms 632 KB Output isn't correct
12 Incorrect 8 ms 760 KB Output isn't correct
13 Incorrect 15 ms 1400 KB Output isn't correct
14 Incorrect 15 ms 1272 KB Output isn't correct
15 Incorrect 19 ms 1528 KB Output isn't correct
16 Incorrect 37 ms 2684 KB Output isn't correct
17 Incorrect 43 ms 3288 KB Output isn't correct
18 Runtime error 26 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 27 ms 4200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 39 ms 3576 KB Output isn't correct