QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105997 | #5420. Inscryption | 0xyz# | WA | 2ms | 3452kb | C++14 | 1.0kb | 2023-05-16 10:35:03 | 2023-05-16 10:35:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,fa[2010],c[2010],ans=0,p[2010];
struct pt{ll 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 ll find(ll x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(ll x,ll 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);
memset(p,-1,sizeof(p));
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
a[0]=a[n];a[n+1]=a[1];
for(ll i=1;i<=n;i++)fa[i]=i;
for(ll 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(ll 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(ll 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(ll i=1;i<=n;i++)
if(i==find(i)&&p[i]<0)ans+=c[i];
cout<<ans<<'\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3452kb
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'