제출 #442351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442351		prvocislo	The Forest of Fangorn (CEOI14_fangorn)	C++17	100 / 100	1291 ms	716 KiB

fangorn

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct bod { ll x, y; };
bool up(const bod &x) { return x.x > 0 || (x.x == 0 && x.y > 0); }
bod sub(const bod &a, const bod &b) { return {a.x-b.x, a.y-b.y}; }
bool cmp(const bod &a, const bod &b) 
{
    bool ua = up(a), ub = up(b);
    if (ua ^ ub) return ua > ub;
    return a.x * b.y - a.y * b.x > 0; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int w, h, nc, nf;
    cin >> w >> h;
    bod g;
    cin >> g.x >> g.y;
    cin >> nc;
    vector<bod> c(nc);
    for (int i = 0; i < nc; i++) cin >> c[i].x >> c[i].y;
    cin >> nf;
    vector<bod> f(nf);
    for (int i = 0; i < nf; i++) cin >> f[i].x >> f[i].y;
    vector<bool> ok(nc, true);
    for (int i = 0; i < nf; i++)
    {
        vector<bod> v;
        for (int j = 0; j < nf; j++) if (i != j) v.push_back(sub(f[i], f[j]));
        sort(v.begin(), v.end(), cmp);
        int pos = (lower_bound(v.begin(), v.end(), sub(g, f[i]), cmp) - v.begin()) % v.size();
        for (int j = 0; j < nc; j++)
        {
            if (!ok[j]) continue;
            int pos2 = (lower_bound(v.begin(), v.end(), sub(c[j], f[i]), cmp) - v.begin()) % v.size();
            if (pos2 ^ pos) ok[j] = false;
        }
    }
    int sz = count(ok.begin(), ok.end(), true);
    cout << sz << "\n";
    for (int i = 0; i < nc; i++) if (ok[i]) cout << i+1 << " ";
    cout << "\n";
    return 0;
}

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