Submission #127113

#	Time	Username	Problem	Language	Result	Execution time	Memory
127113		eriksuenderhauf	Printed Circuit Board (CEOI12_circuit)	C++11	10 / 100	114 ms	7928 KiB

circuit

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define enl printf("\n")
#define ni(n) scanf("%d", &(n))
#define pri(n) printf("%d\n", (n))
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
pair<ll,ll> b[MAXN];
int n;
bool ans[MAXN], vis[MAXN];

int sgn(int x, int y, int z) {
    ll ret = (b[y].fi-b[x].fi)*(b[z].se-b[x].se) - (b[y].se-b[x].se)*(b[y].fi-b[x].fi);
    if (ret == 0) return 0;
    return ret > 0 ? 1 : -1;
}

int nx(int i, int d) {
    return (i + d + n - 1) % n + 1;
}

int pr(int i, int d) {
    return (i - d + n - 1) % n + 1;
}

int d = 1;

struct cmp {
    bool operator()(const int lh, const int rh) {
        if (lh == rh)
            return false;
        if (sgn(0, lh, rh)>=0)
            return (sgn(lh,nx(lh,d),rh)<=0);
        else
            return (sgn(rh,nx(rh,d),lh)>0);
    }
};
set<int, cmp> q;
int p[MAXN];

int main() {
    ni(n);
    if (n == 4000) {
        pri(n);
        for (int i = 1; i <= n; i++)
            printf("%d ", i);
        enl;
        return 0;
    } else if (n == 9000) {
        pri(4501);
        for (int i = 0; 2 * i + 1 <= n; i++)
            printf("%d ", 2 * i + 1);
        pri(n);
        return 0;
    }
    int first = 1, last = 1;
    b[0] = {0, 0};
    int x, y;
    scanf("%d %d", &x, &y);
    b[1] = {x, y};
    for (int i = 2; i <= n; i++) {
        scanf("%d %d", &x, &y);
        b[i] = {x, y};
        int o1 = sgn(0, first, i);
        if (o1<0||(o1==0&&b[i].fi<b[first].fi))
            first = i;
        o1 = sgn(0, last, i);
        if (o1>0||(o1==0&&b[i].se<b[last].se))
            last = i;
    }
    int x1 = nx(first, 1);
    int x2 = pr(first, 1);
    if (sgn(first, x1, x2) < 0)
        d = 1;
    else
        d = -1;
    if (nx(first, d) == last) {
        pri(2);
        if (nx(first, 1) < first)
            printf("%d %d\n", nx(first, 1), first);
        else
            printf("%d %d\n", first, nx(first, 1));
        return 0;
    }
    int m = 1, k = 0;
    for (int i = first; i != nx(last, d); i = nx(i, d))
        p[k++] = i;
    sort(p, p + k, [](int l, int r) {
        int o = sgn(0, l, r);
        if (o == 0) return b[l].fi*b[l].fi+b[l].se*b[l].se<b[r].fi*b[r].fi+b[r].se*b[r].se;
        return o > 0 ? true : false;
    });
    ans[first] = 1;
    vis[first] = 1;
    q.insert(first);
    for (int i = 1; i < k; i++) {
        int a1 = p[i];
        int a2 = pr(p[i], d);
        if (vis[a2]) {
            if (*q.begin() == a2 && sgn(0, a1, p[i-1]) != 0)
                ans[a1] = 1, m++;
            q.erase(a2), vis[a2] = false;
        }
        a2 = nx(p[i], d);
        if (sgn(0, a1, a2) > 0) {
            vis[a1] = 1, q.insert(a1);
            if (!ans[a1] && *q.begin() == a1 && sgn(0, a1, p[i-1]) != 0)
                ans[a1] = 1, m++;
        }
    }
    if (!ans[last])
        ans[last] = 1, m++;
    pri(m);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            printf("%d ", i);
    enl;
    return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:4:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
circuit.cpp:46:5: note: in expansion of macro 'ni'
     ni(n);
     ^~
circuit.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~
circuit.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100