제출 #106642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106642		naoai	Printed Circuit Board (CEOI12_circuit)	C++14	15 / 100	126 ms	11976 KiB

circuit

#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

typedef long long i64;
const int nmax = 1e5 + 5;
const double eps = 1e-7;

struct PCT {
    int x, y;
} c[nmax + 1];

struct segm {
    PCT A, B;
    i64 d;

    segm () {}
    segm (PCT _A, PCT _B) {
        A = _A, B = _B;
        d = 1LL * (A.x + B.x) * (A.x + B.x) + 1LL * (A.y + B.y) * (A.y + B.y);
    }

    bool operator < (const segm &shp) const {
        return d > shp.d;
    }
    bool operator == (const segm &shp) const {
        return (A.x == shp.A.x && A.y == shp.A.y && B.x == shp.B.x && B.y == shp.B.y && d == shp.d);
    }
};

priority_queue<segm> h, hdel; // heap cu lazy deletion

struct pct {
    int x, y, ind;
    i64 d;

    bool operator < (const pct &shp) const {
        if (1LL * y * shp.x != 1LL * x * shp.y) {
            return 1LL * y * shp.x < 1LL * x * shp.y;
        }
        return d < shp.d;
    }
};

vector<pct> v;
vector<int> sol;

void change (int x, int y) {
    i64 dif = 1LL * c[x].y * c[y].x - 1LL * c[y].y * c[x].x;

    if (dif < 0) { // intra
        h.push(segm(c[x], c[y]));
    } else if (dif > 0) { // iese
        hdel.push(segm(c[y], c[x]));
    }
}

segm get_best() {
    while (!hdel.empty() && !h.empty() && h.top() == hdel.top()) {
        h.pop();
        hdel.pop();
    }

    if (h.empty()) {
        segm x;
        x.d = -1;
        return x;
    }
    return h.top();
}

int main() {
    ios::sync_with_stdio(0); fin.tie(nullptr);
    int n;
    fin >> n;

    for (int i = 1; i <= n; ++ i) {
        pct p;
        fin >> p.x >> p.y;

        c[i].x = p.x;
        c[i].y = p.y;

        p.ind = i;
        p.d = 1LL * p.x * p.x + 1LL * p.y * p.y;
        v.push_back(p);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < (int)v.size(); ) {
        int j = i;
        while (j < (int)v.size() && 1LL * v[i].x * v[j].y == 1LL * v[j].x * v[i].y)
            ++ j;

        // doar v[i] poate fi candidat
        segm best = get_best();

        //cout << "!" << v[i].ind <<"\n";
        //cout << best.A.x << " " << best.A.y << " " << best.B.x << " " << best.B.y << " " << best.d << "\n";

        if (best.d != -1) {
            long double panta = (long double)v[i].y / v[i].x;
            long double x = best.A.x + (best.A.y - panta * best.A.x) * (best.B.x - best.A.x) /
                                        (panta * (best.B.x - best.A.x) - (best.B.y - best.A.y));

            if (fabs(v[i].x - x) <= eps || v[i].x < x)
                sol.push_back(v[i].ind);
        } else {
            sol.push_back(v[i].ind);
        }

        // adaug / scot segm noi
        while (i < j) {
            int u = v[i].ind;

            int ant = u - 1;
            if (ant == 0) ant = n;

            change(u, ant);

            int nxt = u + 1;
            if (nxt == n + 1) nxt = 1;

            change(u, nxt);

            ++ i;
        }
    }

    cout << sol.size() << "\n";
    sort(sol.begin(), sol.end());
    for (auto i : sol)
        cout << i << " ";
    cout << "\n";

    return 0;
}

• Subtask 1: 15 / 100