Submission #52250

#	Time	Username	Problem	Language	Result	Execution time	Memory
52250		Alexa2001	The Forest of Fangorn (CEOI14_fangorn)	C++17	50 / 100	3065 ms	1044 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

const int Qmax = 10005, Nmax = 2005;
const double PI = acos(-1);

int Lines, Rows, L, C, N, Q, p, i, j, ans;
bool good[Qmax];

struct point
{
    int x, y;
    point operator - (const point &other) const
    {
        return {x - other.x, y - other.y};
    }
};
vector<point> A;
point a[Nmax], S, q[Qmax];

bool cmp(point a, point b)
{
    double p1 = atan2(a.y, a.x), p2 = atan2(b.y, b.x);
    if(p1 < 0) p1 += 2*PI;
    if(p2 < 0) p2 += 2*PI;
    return p1 < p2;
}

int Find(point P)
{
    int st = 0, dr = A.size() - 1, mid;

    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(cmp(P, A[mid])) dr = mid-1;
            else st = mid+1;
    }

    return st % A.size();
}

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    cin >> Lines >> Rows >> S.x >> S.y;

    cin >> Q;
    for(i=1; i<=Q; ++i) cin >> q[i].x >> q[i].y, good[i] = 1;

    cin >> N;
    for(i=1; i<=N; ++i) cin >> a[i].x >> a[i].y;

    ans = Q;
    for(i=1; i<=N; ++i)
    {
        A.clear();

        for(j=1; j<=N; ++j)
            if(i != j) A.push_back(a[i] - a[j]);

        sort(A.begin(), A.end(), cmp);

        p = Find(S - a[i]);

        for(j=1; j<=Q; ++j)
            if(good[j] && Find(q[j] - a[i]) != p) good[j] = 0, --ans;
    }

    cout << ans << '\n';
    for(i=1; i<=Q; ++i)
        if(good[i]) cout << i << ' ';

    return 0;
}

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