oj.uz

Submission #52252

# Submission time Handle Problem Language Result Execution time Memory
52252 2018-06-25T06:33:06 Z Alexa2001 The Forest of Fangorn (CEOI14_fangorn) C++17
0 / 100
 3000 ms 768 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];

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

bool ord(point a, point b, point c)
{
    a = a-c, b = b-c;
    return (ll)a.x * b.y > (ll)a.y * b.x;
}

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]);
        if(!p) r = A.size() - 1;
            else r = p - 1;

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

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

    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Correct 2 ms 484 KB Output is correct
3 Incorrect 2 ms 568 KB Output isn't correct
4 Incorrect 2 ms 640 KB Output isn't correct
5 Incorrect 3 ms 640 KB Output isn't correct
6 Incorrect 2 ms 640 KB Output isn't correct
7 Incorrect 6 ms 736 KB Output isn't correct
8 Incorrect 5 ms 736 KB Output isn't correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 736 KB Output is correct
2 Incorrect 4 ms 736 KB Output isn't correct
3 Incorrect 6 ms 736 KB Output isn't correct
4 Correct 9 ms 736 KB Output is correct
5 Correct 9 ms 736 KB Output is correct
6 Correct 19 ms 748 KB Output is correct
7 Incorrect 2 ms 748 KB Output isn't correct
8 Correct 3 ms 748 KB Output is correct
9 Incorrect 6 ms 748 KB Output isn't correct
10 Incorrect 46 ms 748 KB Output isn't correct
11 Incorrect 27 ms 764 KB Output isn't correct
12 Correct 44 ms 768 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -