oj.uz

Submission #538398

# Submission time Handle Problem Language Result Execution time Memory
538398 2022-03-16T18:05:20 Z Sorting The Forest of Fangorn (CEOI14_fangorn) C++17
10 / 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 all(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];

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

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

bool on_line(ll x1, ll y1, ll x2, ll y2, ll x3, ll 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 intersectLine(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4){
    ll a1 = sign(orient(x1, y1, x2, y2, x3, y3));
    ll a2 = sign(orient(x1, y1, x2, y2, x4, y4));
    ll a3 = sign(orient(x3, y3, x4, y4, x1, y1));
    ll a4 = sign(orient(x3, y3, x4, y4, x2, y2));

    return (a3 * a4) <= 0;
}

bool intersectSegments(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4){
    ll a1 = sign(orient(x1, y1, x2, y2, x3, y3));
    ll a2 = sign(orient(x1, y1, x2, y2, x4, y4));
    ll a3 = sign(orient(x3, y3, x4, y4, x1, y1));
    ll 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;
}


bool check(ll x1, ll y1, ll x2, ll y2){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            bool in1 = intersectSegments(x1, y1, x2, y2, tp[i].first, tp[i].second, tp[j].first, tp[j].second);
            if(intersectLine(x1, y1, x2, y2, tp[i].first, tp[i].second, tp[j].first, tp[j].second)){
                if(!in1){
                    return false;
                }
            }
        }
    }

    return true;
}

bool check2(ll x, ll 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;
    }

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

Compilation message

fangorn.cpp: In function 'bool intersectLine(ll, ll, ll, ll, ll, ll, ll, ll)':
fangorn.cpp:33:8: warning: unused variable 'a1' [-Wunused-variable]
   33 |     ll a1 = sign(orient(x1, y1, x2, y2, x3, y3));
      |        ^~
fangorn.cpp:34:8: warning: unused variable 'a2' [-Wunused-variable]
   34 |     ll a2 = sign(orient(x1, y1, x2, y2, x4, y4));
      |        ^~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 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 1 ms 212 KB Output isn't correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct

Subtask #2
10.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 1 ms 212 KB Output is correct
4 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 212 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 4 ms 336 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 0 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 3095 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -