Submission #52258

#	Time	Username	Problem	Language	Result	Execution time	Memory
52258		Alexa2001	The Forest of Fangorn (CEOI14_fangorn)	C++17	100 / 100	1848 ms	1396 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

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

int Lines, Rows, L, C, N, Q, p, i, j, r, 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];

inline bool cross(point a, point b)
{
    return (ll)a.x * b.y > (ll)a.y * b.x;
}

inline bool up(point a)
{
    return a.x > 0 | (a.x == 0 && a.y > 0);
}

bool cmp(point a, point b)
{
    if(up(a) != up(b)) return up(a);
    return cross(a, b);
}

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;
}

Compilation message (stderr)

fangorn.cpp: In function 'bool up(point)':
fangorn.cpp:30:16: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
     return a.x > 0 | (a.x == 0 && a.y > 0);
            ~~~~^~~

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