QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#644999 | #5426. Drain the Water Tank | tsai | WA | 0ms | 3916kb | C++14 | 1.5kb | 2024-10-16 16:24:38 | 2024-10-16 16:24:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct node{
int x;
int y;
}no[1000050];
//vector<node>v;
vector<int>tem;
bool check(int l,int r,int mid){
int y1=no[mid].y-no[l].y;
int x1=no[mid].x-no[l].x;
int x2=no[r].x-no[l].x;
int y2=no[r].y-no[l].y;
return ((x1*y2-x2*y1)>0);
}
void solve(){
int n;
scanf("%d",&n);
int st=0;
for(int i=0;i<=n-1;i++){
scanf("%d %d",&no[i].x,&no[i].y);
}
for(int i=0;i<n-1;i++){
if(no[i+1].y==no[i].y){
st++;
}else{
break;
}
}
int l=st,mid,r;
mid=(l+1)%n;r=(mid+1)%n;
int cnt=0;
while(1){
tem.clear();
while(no[r].y==no[mid].y){
tem.push_back(mid);
mid++;
mid%=n;
r=(mid+1)%n;
}
int now=0;
r=(mid+1)%n;
for(auto mi:tem){
if(no[l].y>no[mi].y&&no[r].y>no[mi].y){
if(check(l,r,mi)){
now++;
}
}
}
if(no[l].y>no[mid].y&&no[r].y>no[mid].y){
if(check(l,r,mid)){
now++;
}
}
cnt+=(now>0);
l=mid;mid++;
mid%=n;
r=(mid+1)%n;
if(l==st){
break;
}
}
printf("%d",cnt);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--){
solve();
if(t) printf("\n");
}
return 0;
}
/*
10
1 0
2 0
3 0
2 1
3 2
2 2
1 2
0 2
1 1
0 0
//1
6
0 0
2 0
1 1
4 1
5 0
3 4
//2
16
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10
//2
16
2 0
3 0
3 1
5 1
5 6
0 6
0 4
1 4
1 3
2 3
2 5
3 5
3 3
4 3
4 2
2 2
//2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
8 4 4 0 4 0 2 1 2 2 2 2 0 3 0 4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 1 0 3 4 0 3 1 2 2 3 1 1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 0 0 170 0 140 30 60 30 0 70
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
5 0 0 1 2 1 5 0 2 0 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3852kb
input:
3 0 0 100 0 0 100
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'