oj.uz

Submission #538390

# Submission time Handle Problem Language Result Execution time Memory
538390 2022-03-16T17:51:34 Z Sorting The Forest of Fangorn (CEOI14_fangorn) C++17
20 / 100
 3000 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define a__int128(x) (x).begin(), (x).end()

const ll N = 2000 + 3;
const ll C = 1e4 + 3;
const ll INF = 1e9;

ll n, c, w, h;
ll x, y;
pair<ll, ll> cp[C], tp[N];

__int128 orient(__int128 x1, __int128 y1, __int128 x2, __int128 y2, __int128 x3, __int128 y3){
    return x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}

__int128 sign(__int128 x){
    return (x == 0) ? 0 : ((x > 0) ? 1 : -1);
}

bool on_line(__int128 x1, __int128 y1, __int128 x2, __int128 y2, __int128 x3, __int128 y3){
    if(orient(x1, y1, x2, y2, x3, y3)) return false;
    return min(x1, x2) <= x3 && x3 <= max(x1, x2) && min(y1, y2) <= y3 && y3 <= max(y1, y2);
}

bool intersect(__int128 x1, __int128 y1, __int128 x2, __int128 y2, __int128 x3, __int128 y3, __int128 x4, __int128 y4){
    __int128 a1 = sign(orient(x1, y1, x2, y2, x3, y3));
    __int128 a2 = sign(orient(x1, y1, x2, y2, x4, y4));
    __int128 a3 = sign(orient(x3, y3, x4, y4, x1, y1));
    __int128 a4 = sign(orient(x3, y3, x4, y4, x2, y2));

    if(on_line(x1, y1, x2, y2, x3, y3) && on_line(x1, y1, x2, y2, x4, y4))
        return true;
    if(on_line(x3, y3, x4, y4, x1, y1) && on_line(x3, y3, x4, y4, x2, y2))
        return true;

    if(!a1 || !a2 || !a3 || !a4)
        return false;

    if(a1 != a2 && a3 != a4)
        return true;

    return false;
}

array<__int128, 4> segmentToLine(__int128 x1, __int128 y1, __int128 x2, __int128 y2){
    __int128 x3 = x1 + (x1 - x2) * INF;
    __int128 y3 = y1 + (y1 - y2) * INF;
    __int128 x4 = x2 + (x2 - x1) * INF;
    __int128 y4 = y2 + (y2 - y1) * INF;
    return array<__int128, 4>{x3, y3, x4, y4};
}

bool check(__int128 x1, __int128 y1, __int128 x2, __int128 y2){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            auto [x3, y3, x4, y4] = segmentToLine(tp[i].first, tp[i].second, tp[j].first, tp[j].second);
            bool in1 = intersect(x1, y1, x2, y2, tp[i].first, tp[i].second, tp[j].first, tp[j].second);
            bool in2 = intersect(x1, y1, x2, y2, x3, y3, x4, y4);
            if(in2){
                if(!in1){
                    return false;
                }
            }
        }
    }

    return true;
}

bool check2(__int128 x, __int128 y){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(orient(tp[i].first, tp[i].second, tp[j].first, tp[j].second, x, y) == 0){
                if(!on_line(tp[i].first, tp[i].second, tp[j].first, tp[j].second, x, y))
                    return false;
            }
        }
    }

    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> w >> h >> x >> y;

    cin >> c;
    for(int i = 0; i < c; ++i){
        cin >> cp[i].first >> cp[i].second;
    }

    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> tp[i].first >> tp[i].second;
    }

    __int128 midx = 0, midy = 0;
    for(int i = 0; i < n; ++i){
        midx += tp[i].first;
        midy += tp[i].second;
    }

    midx /= n;
    midy /= n;

    vector<int> ans;
    for(int i = 0; i < c; ++i){
        if(!check2(cp[i].first, cp[i].second))
            continue;

        if(check(x, y, cp[i].first, cp[i].second))
            ans.push_back(i + 1);
        else if(check(x, y, midx, midy) && check(midx, midy, cp[i].first, cp[i].second))
            ans.push_back(i + 1);
    }

    cout << ans.size() << "\n";
    for(int x: ans)
        cout << x << " ";
    cout << "\n";
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 3 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 21 ms 332 KB Output is correct
11 Correct 29 ms 340 KB Output is correct
12 Correct 20 ms 212 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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