oj.uz

Submission #312090

# Submission time Handle Problem Language Result Execution time Memory
312090 2020-10-12T10:13:37 Z FatihSolak Relay (COI16_relay) C++14
0 / 100
 37 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;
bool ccw(long long A_x, long long A_y,long long B_x,long long B_y,long long C_x,long long C_y){
    return (C_y-A_y)*(B_x-A_x) < (B_y-A_y)*(C_x-A_x);
}
bool intersect(long long A_x, long long A_y,long long B_x,long long B_y,long long C_x,long long C_y,long long D_x,long long D_y){
        return ccw(A_x,A_y,C_x,C_y,D_x,D_y) != ccw(B_x,B_y,C_x,C_y,D_x,D_y) and ccw(A_x,A_y,B_x,B_y,C_x,C_y) != ccw(A_x,A_y,B_x,B_y,D_x,D_y);
}
int main(){
    int n,m;
    cin >> n;
    long long ships[n][2];
    int visited[n];
    for(int i=0;i<n;i++){
        cin >> ships[i][0] >> ships[i][1];
        visited[i] = 0;
    }
    cin >> m;
    long long p[m][2];
    for(int i=0;i<m;i++){
        cin >> p[i][0] >> p[i][1];
    }
    int ans=0;
    for(int i=1;i<n;i++){
        int num=0;
        for(int j=0;j<m;j++){
            int before = (j+1)%m;
            if(intersect(ships[0][0],ships[0][1],ships[i][0],ships[i][1],p[before][0],p[before][1],p[j][0],p[j][1])){
                num++;
            }
            if(j==m-1 && num<2){
                visited[i] = 1;
                ans++;
            }
        }
    }
    for(int i=1;i<n;i++){
        if(visited[i] == 1){
            for(int j=1;j<n;j++){
                if(!visited[j]){
                    int num=0;
                    for(int c=0;c<m;c++){
                        int before = (c+1)%m;
                        if(intersect(ships[i][0],ships[i][1],ships[j][0],ships[j][1],p[before][0],p[before][1],p[c][0],p[c][1])){
                            num++;
                        }
                        if(c==m-1 && num<2){
                            visited[i] = 2;
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout <<ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -