QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714036 | #7906. Almost Convex | k1rito | TL | 1ms | 4240kb | C++14 | 2.3kb | 2024-11-05 21:19:37 | 2024-11-05 21:19:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db double
const int mod=1e9+7;
const int N=2e3+10;
const db PI=acos(-1);
const db eps=1e-14;
int n,tp,s[N],whe[N],T,vis[N],ans,m,now,st[N];
struct V
{
db x,y;
int id;
}a[N],b[N];
db calcompare(db x,db y,db xx,db yy)
{
return x*yy-xx*y;
}
bool cmp(V a,V b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(V A,V B)
{
V c;
c=a[now];
if(calcompare(A.x-c.x,A.y-c.y,B.x-c.x,B.y-c.y)==0)
return A.x<B.x;
else return calcompare(A.x-c.x,A.y-c.y,B.x-c.x,B.y-c.y)>0;
}
bool cmp3(V A,V b)
{
V c;
c=a[now];
if(atan2(A.y-c.y,A.x-c.x)!=atan2(b.y-c.y,b.x-c.x))
return atan2(A.y-c.y,A.x-c.x)<atan2(b.y-c.y,b.x-c.x);
else return A.x<b.x;
}
void solve()
{
m=0;
for(int i=1;i<=n;i++)
{
if(i==now) continue;
b[++m]=a[i];b[m].id=i;
}
sort(b+1,b+1+m,cmp3);
//cout<<now<<" start "<<endl;
for(int i=1;i<=m;i++)
{
//cout<<i<<" : "<<b[i].x<<" "<<b[i].y<<endl;
st[b[i].id]=i;
}
for(int i=1;i<tp;i++)
{
if(abs(st[s[i]]-st[s[i+1]])==1||abs(st[s[i]]-st[s[i+1]])==m-1)
ans++;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
s[++tp]=1;
for(int i=2;i<=n;i++)
{
while(tp>=2&&calcompare(a[s[tp]].x-a[s[tp-1]].x,a[s[tp]].y-a[s[tp-1]].y,a[i].x-a[s[tp]].x,a[i].y-a[s[tp]].y)<=0)
{
tp--;
whe[s[tp+1]]=0;
}
s[++tp]=i;
whe[i]=1;
}
int sum1=tp;
for(int i=n-1;i>=1;i--)
{
if(!whe[i])
{
while(tp>sum1&&calcompare(a[s[tp]].x-a[s[tp-1]].x,a[s[tp]].y-a[s[tp-1]].y,a[i].x-a[s[tp]].x,a[i].y-a[s[tp]].y)<=0)
{
tp--;
whe[s[tp+1]]=0;
}
s[++tp]=i;
whe[i]=1;
}
}
for(int i=1;i<=tp;i++)
{
vis[s[i]]=1;
//cout<<s[i]<<"asdasd "<<a[s[i]].x<<" "<<a[s[i]].y<<endl;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]) now=i,solve();
}
cout<<ans+1;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4240kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4208kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4176kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...