oj.uz

Submission #483867

# Submission time Handle Problem Language Result Execution time Memory
483867 2021-11-01T06:06:28 Z sam571128 Geometrija (COCI21_geometrija) C++17
50 / 110
 1000 ms 664 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

typedef pair<int,int> point;
#define x first
#define y second

int operator^(point a, point b){
    return a.x*b.y-a.y*b.x;
}

int operator*(point a, point b){
    return a.x*b.x+a.y*b.y;
}

point operator-(point a, point b){
    return {a.x-b.x,a.y-b.y};
}

point operator+(point a, point b){
    return {a.x+b.x,a.y+b.y};
}

int ori(point a, point b, point c){
    int tmp = (b-a)^(c-a);
    if(tmp == 0) return 0;
    return abs(tmp)/tmp;
}
int intersect(point a, point b, point c, point d){
    int abc = ori(a,b,c);
    int abd = ori(a,b,d);
    int cda = ori(c,d,a);
    int cdb = ori(c,d,b);

    if(abc*abd < 0 && cda*cdb < 0) return true;
    else return false;
}

signed main(){
    fastio

    int n;
    cin >> n;
    vector<point> arr;
    for(int i = 0;i < n;i++){
        int a,b;
        cin >> a >> b;
        arr.push_back({a,b});
    }

    int ans = 0;
    vector<pair<point,point>> tr;
    for(int a = 0; a < n; a++){
        for(int b = a+1; b < n; b++){
            for(auto [c,d] : tr){
                if(intersect(arr[a],arr[b],c,d)){
                    goto nxt;    
                }
            } 

            tr.push_back({arr[a],arr[b]});

            for(int c = 0;c < n;c++){
                for(int d = c+1; d < n;d++){
                    if(intersect(arr[a],arr[b],arr[c],arr[d])){
                        goto nxt;
                    }
                }
            }

            ans++;

            nxt:;
        }
    }
    cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 13 ms 352 KB Output is correct
13 Correct 13 ms 376 KB Output is correct
14 Correct 9 ms 348 KB Output is correct
15 Correct 8 ms 332 KB Output is correct
16 Correct 33 ms 352 KB Output is correct
17 Correct 23 ms 356 KB Output is correct
18 Correct 16 ms 332 KB Output is correct
19 Correct 15 ms 340 KB Output is correct
20 Correct 70 ms 332 KB Output is correct
21 Correct 67 ms 348 KB Output is correct
22 Correct 12 ms 332 KB Output is correct
23 Correct 14 ms 384 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 13 ms 352 KB Output is correct
13 Correct 13 ms 376 KB Output is correct
14 Correct 9 ms 348 KB Output is correct
15 Correct 8 ms 332 KB Output is correct
16 Correct 33 ms 352 KB Output is correct
17 Correct 23 ms 356 KB Output is correct
18 Correct 16 ms 332 KB Output is correct
19 Correct 15 ms 340 KB Output is correct
20 Correct 70 ms 332 KB Output is correct
21 Correct 67 ms 348 KB Output is correct
22 Correct 12 ms 332 KB Output is correct
23 Correct 14 ms 384 KB Output is correct
24 Correct 363 ms 456 KB Output is correct
25 Correct 295 ms 448 KB Output is correct
26 Correct 335 ms 560 KB Output is correct
27 Correct 312 ms 664 KB Output is correct
28 Correct 349 ms 552 KB Output is correct
29 Correct 199 ms 440 KB Output is correct
30 Correct 246 ms 452 KB Output is correct
31 Execution timed out 1062 ms 384 KB Time limit exceeded
32 Halted 0 ms 0 KB -