oj.uz

Submission #538389

# Submission time Handle Problem Language Result Execution time Memory
538389 2022-03-16T17:50:07 Z Sorting The Forest of Fangorn (CEOI14_fangorn) C++17
10 / 100
 3000 ms 348 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 ald(x) (x).begin(), (x).end()

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

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

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

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

bool on_line(ld x1, ld y1, ld x2, ld y2, ld x3, ld 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(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3, ld x4, ld y4){
    ld a1 = sign(orient(x1, y1, x2, y2, x3, y3));
    ld a2 = sign(orient(x1, y1, x2, y2, x4, y4));
    ld a3 = sign(orient(x3, y3, x4, y4, x1, y1));
    ld 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<ld, 4> segmentToLine(ld x1, ld y1, ld x2, ld y2){
    ld x3 = x1 + (x1 - x2) * INF;
    ld y3 = y1 + (y1 - y2) * INF;
    ld x4 = x2 + (x2 - x1) * INF;
    ld y4 = y2 + (y2 - y1) * INF;
    return array<ld, 4>{x3, y3, x4, y4};
}

bool check(ld x1, ld y1, ld x2, ld 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(ld x, ld 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;
    }

    ld 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 0 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 212 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 4 ms 280 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Correct 4 ms 212 KB Output is correct
10 Correct 36 ms 340 KB Output is correct
11 Correct 47 ms 340 KB Output is correct
12 Correct 30 ms 348 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 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 3046 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -