Submission #312088

#	Time	Username	Problem	Language	Result	Execution time	Memory
312088		FatihSolak	Relay (COI16_relay)	C++14	0 / 100	13 ms	256 KiB

relay

#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++){
        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])){
                break;
            }
            else if(j==m-1){
                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]){
                    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])){
                            break;
                        }
                        else if(c==m-1){
                            visited[i] = 2;
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout <<ans;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43