| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 312097 |
2020-10-12T11:09:38 Z |
FatihSolak |
Relay (COI16_relay) |
C++14 |
|
40 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);
}
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;
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])){
num++;
}
num+=2;
}
if(j==m-1 && num<3){
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])){
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])){
num++;;
}
num+=2;
}
if(c==m-1 && num<2){
visited[i] = 2;
ans++;
}
}
}
}
}
}
cout <<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
