oj.uz

Submission #52258

# Submission time Handle Problem Language Result Execution time Memory
52258 2018-06-25T06:57:33 Z Alexa2001 The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 1848 ms 1396 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 3 ms 648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 648 KB Output is correct
2 Correct 2 ms 648 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 2 ms 700 KB Output is correct
9 Correct 2 ms 700 KB Output is correct
10 Correct 6 ms 700 KB Output is correct
11 Correct 6 ms 700 KB Output is correct
12 Correct 6 ms 700 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 118 ms 700 KB Output is correct
5 Correct 26 ms 700 KB Output is correct
6 Correct 536 ms 700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 764 KB Output is correct
2 Correct 1848 ms 1096 KB Output is correct
3 Correct 580 ms 1264 KB Output is correct
4 Correct 1046 ms 1396 KB Output is correct