QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672977#5426. Drain the Water TankPDF_vegetableWA 2ms12020kbC++142.5kb2024-10-24 20:07:422024-10-24 20:07:42

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 20:07:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12020kb
  • [2024-10-24 20:07:42]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define LL long long
#define MAXN 1000000
#define INF 1000000000000000
#define Pr pair<int,int>
#define X first
#define Y second

LL read(){
    LL x=0,F=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*F;
}

int n,pn;
LL nx[MAXN+5],ny[MAXN+5];
int ans;
Pr p[MAXN+5];
int twx[MAXN+5],twy[MAXN+5];

int main(){
    n=read();
    if(n==3){
        puts("1");
        return 0;
    }
    for(int i=0;i<n;i++)
        nx[i]=read(),ny[i]=read();
    for(int i=0;i<n;i++){
        int pre=(i-1+n)%n,suf=(i+1)%n;
        if(ny[pre]==ny[i]&&ny[suf]==ny[i])continue;
        else if(nx[pre]==nx[i]&&nx[suf]==nx[i])continue;
        else p[pn++]=Pr(nx[i],ny[i]);
    }
    n=pn;
    for(int i=0;i<n;i++){
        int pre=0,suf=0;
        if(p[i].Y==p[(i+1)%n].Y){
            pre=(i-1+n)%n;
            suf=(i+2)%n;
            if(p[i].Y<p[pre].Y&&p[i].Y<p[suf].Y){
                twx[i]=1;
                //printf("::%d %d\n",p[i].X,p[i].Y);
            }
        }
        else{
            pre=(i-1+n)%n;
            suf=(i+1)%n;
            if(p[i].Y<p[pre].Y&&p[i].Y<p[suf].Y){
                twx[i]=1;
                //printf("::%d %d\n",p[i].X,p[i].Y);
            }
        }
        if((p[i].X-p[pre].X)*(p[i].X-p[suf].X)>0){
            twy[i]=1;
            //printf("**%d %d\n",p[i].X,p[i].Y);
        }
    }
    for(int i=0;i<n;i++)
    if(twx[i]){
        int j=(i+1)%n;
        int cnt=0;
        int pre=(i+1)%n,lst=(i-1+n)%n;
        while(j!=lst){
            int ax=p[j].X,ay=p[j].Y;
            int bx=p[(j+1)%n].X,by=p[(j+1)%n].Y;
            if((ax-p[i].X)*(bx-p[i].X)<0){
                //printf("%d %d -> %d %d\n",ax,ay,bx,by);
                if(bx<ax){
                    swap(ax,bx);
                    swap(ay,by);
                }
                if((p[i].X-ax)*(p[i].Y-by)-(p[i].X-bx)*(p[i].Y-ay)<0)
                    cnt++;
            }else if(j!=pre&&p[i].X==ax&&p[i].Y<ay){
                if(!twy[j])cnt++;
            }
            j=(j+1)%n;
        }
        if(p[i].X==p[pre].X)
            cnt+=((p[i].X-p[(pre+1)%n].X)*(p[i].X-p[lst].X)>0);
        if(p[i].X==p[lst].X)
            cnt+=((p[i].X-p[(lst+n-1)%n].X)*(p[i].X-p[pre].X)>0);
        //printf("%d %d %d\n",cnt,p[i].X,p[i].Y);
        if(cnt%2==1)ans++;
    }
    printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11940kb

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: 11936kb

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: 2ms
memory: 11948kb

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: -100
Wrong Answer
time: 0ms
memory: 12020kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

0

result:

wrong answer 1st numbers differ - expected: '2', found: '0'