oj.uz

Submission #312105

# Submission time Handle Problem Language Result Execution time Memory
312105 2020-10-12T11:25:08 Z FatihSolak Relay (COI16_relay) C++14
0 / 100
 41 ms 512 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);
}
bool onSegment(long long A_x, long long A_y,long long B_x, long long B_y, long long C_x, long long C_y) 
{ 
    if (B_x <= max(A_x, C_x) && B_x >= min(A_x, C_x) && 
        B_y <= max(A_y, C_y) && B_y >= min(A_y, C_y)) 
       return true; 
    return false; 
} 
int orientation(long long A_x, long long A_y,long long B_x, long long B_y,long long C_x, long long C_y) 
{ 
    int val = (B_y - A_y) * (C_x - B_x) - 
              (B_x - A_x) * (C_y - B_y); 
  
    if (val == 0) return 0;
  
    return (val > 0)? 1: 2;
} 

bool intersect1(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) 
{ 
    int o1 = orientation(A_x, A_y, B_x,B_y, C_x,C_y); 
    int o2 = orientation(A_x, A_y, B_x,B_y, D_x,D_y); 
    int o3 = orientation(C_x,C_y, D_x,D_y, A_x, A_y); 
    int o4 = orientation(C_x,C_y, D_x,D_y, B_x,B_y); 
  
    // General case 
    if (o1 != o2 && o3 != o4) 
        return true; 
  
    
    if (o1 == 0 && onSegment(A_x, A_y, C_x,C_y, B_x,B_y)) return true; 
  
 
    if (o2 == 0 && onSegment(A_x, A_y, D_x,D_y, B_x,B_y)) return true; 
  
    if (o3 == 0 && onSegment(C_x,C_y, A_x, A_y, D_x,D_y)) return true; 
  
    if (o4 == 0 && onSegment(C_x,C_y, B_x,B_y, D_x,D_y)) return true; 
  
    return false; // Doesn't fall in any of the above cases 
}
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,cnt=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])){
                if(intersect1(ships[0][0],ships[0][1],ships[i][0],ships[i][1],p[before][0],p[before][1],p[before][0],p[before][1])+intersect1(ships[0][0],ships[0][1],ships[i][0],ships[i][1],p[j][0],p[j][1],p[j][0],p[j][1])){
                    cnt++;
                }
                else{
                    num++;
                }
            }
            if(j==m-1 &&( cnt<4&&num<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]){
                    int num=0,cnt=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])){
                            if(intersect1(ships[i][0],ships[i][1],ships[j][0],ships[j][1],p[before][0],p[before][1],p[before][0],p[before][1])+intersect1(ships[i][0],ships[i][1],ships[j][0],ships[j][1],p[j][0],p[j][1],p[j][0],p[j][1])){
                                cnt++;
                            }
                            else{
                                num++;
                            }
                        }
                        if(c==m-1 && (cnt<4 && num<1)){
                            visited[j] = 2;
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout <<ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 256 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Incorrect 17 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 256 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Incorrect 17 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 256 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Incorrect 17 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 256 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Incorrect 17 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -