oj.uz

답안 #140291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140291 2019-08-02T13:25:15 Z egorlifar Printed Circuit Board (CEOI12_circuit) C++17
0 / 100
 43 ms 2936 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;
    vector<int> f;
    for (int i = 0; i <= uk; i++) {
        f.pb(q[i].id);
    }
    for (int i = uk1; i < n; i++) {
        f.pb(q[i].id);
    }
    sort(all(f));
    for (auto x: f) {
        cout << x << ' ';
    }
    cout << endl;
    return 0; 
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 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 376 KB Output isn't correct
5 Incorrect 6 ms 504 KB Output isn't correct
6 Incorrect 6 ms 504 KB Output isn't correct
7 Incorrect 10 ms 632 KB Output isn't correct
8 Incorrect 5 ms 504 KB Output isn't correct
9 Incorrect 9 ms 504 KB Output isn't correct
10 Incorrect 7 ms 504 KB Output isn't correct
11 Incorrect 15 ms 476 KB Output isn't correct
12 Incorrect 8 ms 504 KB Output isn't correct
13 Incorrect 16 ms 1144 KB Output isn't correct
14 Incorrect 15 ms 888 KB Output isn't correct
15 Incorrect 19 ms 892 KB Output isn't correct
16 Incorrect 35 ms 1528 KB Output isn't correct
17 Incorrect 43 ms 1912 KB Output isn't correct
18 Runtime error 26 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 26 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 39 ms 2040 KB Output isn't correct