oj.uz

Submission #538387

# Submission time Handle Problem Language Result Execution time Memory
538387 2022-03-16T17:48:12 Z Sorting The Forest of Fangorn (CEOI14_fangorn) C++17
10 / 100
 3000 ms 468 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;
    w *= 2, h *= 2;
    x *= 2, y *= 2;


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

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

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

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 3 ms 368 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 244 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 27 ms 328 KB Output is correct
11 Correct 45 ms 352 KB Output is correct
12 Correct 32 ms 324 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 324 KB Output is correct
3 Incorrect 1 ms 332 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 3067 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -