Submission #554731

#	Time	Username	Problem	Language	Result	Execution time	Memory
554731		alextodoran	The Forest of Fangorn (CEOI14_fangorn)	C++17	50 / 100	3091 ms	11572 KiB

fangorn

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int T_MAX = 2000;
const int C_MAX = 10000;

struct Point {
    int x, y;
};

int W, H;
int T, C;
Point me;
Point trees[T_MAX + 2];
Point camps[C_MAX + 2];

ld ang (const Point &a, const Point &b) {
    return atan2(b.y - a.y, b.x - a.x);
}

int id[T_MAX + 2][C_MAX + 2];
int tperm[T_MAX + 2], cperm[C_MAX + 2];
void splitBy (int t) {
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = 2 * trees[t].x - trees[t1].x;
        trees[t1].y = 2 * trees[t].y - trees[t1].y;
    }
    iota(tperm + 1, tperm + T + 1, 1);
    swap(tperm[t], tperm[T]);
    sort(tperm + 1, tperm + (T - 1) + 1, [&] (const int &t1, const int &t2) {
        return ang(trees[t], trees[t1]) < ang(trees[t], trees[t2]);
    });
    iota(cperm + 1, cperm + C + 1, 1);
    sort(cperm + 1, cperm + C + 1, [&] (const int &c1, const int &c2) {
        return ang(trees[t], camps[c1]) < ang(trees[t], camps[c2]);
    });
    for (int ci = 1, ti = 0; ci <= C; ci++) {
        while (ti + 1 < T && ang(trees[t], trees[tperm[ti + 1]]) < ang(trees[t], camps[cperm[ci]])) {
            ti++;
        }
        id[t][cperm[ci]] = (ti > 0 ? ti : T - 1);
    }
    for (int t1 = 1; t1 <= T; t1++) {
        trees[t1].x = 2 * trees[t].x - trees[t1].x;
        trees[t1].y = 2 * trees[t].y - trees[t1].y;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> W >> H;
    cin >> me.x >> me.y;
    cin >> C;
    for (int c = 1; c <= C; c++) {
        cin >> camps[c].x >> camps[c].y;
    }
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> trees[t].x >> trees[t].y;
    }
    camps[++C] = me;

    for (int t = 1; t <= T; t++) {
        splitBy(t);
    }

    vector <int> reach;
    for (int c = 1; c < C; c++) {
        bool ok = true;
        for (int t = 1; t <= T; t++) {
            if (id[t][c] != id[t][C]) {
                ok = false;
                break;
            }
        }
        if (ok == true) {
            reach.push_back(c);
        }
    }
    cout << (int) reach.size() << "\n";
    for (int c : reach) {
        cout << c << " ";
    }
    cout << "\n";

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20