QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105994 | #5420. Inscryption | 0xyz# | WA | 2ms | 3352kb | C++14 | 1.0kb | 2023-05-16 10:24:20 | 2023-05-16 10:24:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,fa[2010],c[2010],ans=0,p[2010];
struct pt{int x,y;}a[2010];
inline bool cross(pt p,pt q,pt r){
int x_1,y_1,x_2,y_2;
x_1=p.x-q.x;y_1=p.y-q.y;
x_2=r.x-q.x;y_2=r.y-q.y;
return x_1*y_2<=x_2*y_1;
}
inline int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fx]=fy;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
memset(p,-1,sizeof(p));
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
a[0]=a[n];a[n+1]=a[1];
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=2;i<=n;i++)
if(a[i].y==a[i-1].y)merge(i,i-1);
if(a[1].y==a[n].y)merge(1,n);
for(int i=1;i<=n;i++)
if(a[i].y<=a[i-1].y&&a[i].y<=a[i+1].y&&cross(a[i-1],a[i],a[i+1]))c[find(i)]=1;
for(int i=1;i<=n;i++)
if(a[i].y>a[i+1].y)p[find(i)]=i+1;
else if(a[i].y>a[i-1].y)p[find(i)]=i-1;
for(int i=1;i<=n;i++)
if(i==find(i)&&p[i]<0)ans+=c[i];
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3352kb
input:
6 7 1 1 1 -1 1 1 -1 4 1 0 -1 0 4 0 -1 -1 0 1 0 2 0 0 1 -1
output:
2
result:
wrong answer 1st lines differ - expected: '3 2', found: '2'