QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734490 | #7906. Almost Convex | xinlengweishang | WA | 496ms | 8208kb | C++20 | 2.9kb | 2024-11-11 11:27:14 | 2024-11-11 11:27:14 |
Judging History
answer
#include<bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;
struct node{
ll x;
ll y;
}t[maxn],s[maxn],sup[maxn],sdown[maxn];
ll x;
ll n;
ll check(node a,node b,node c,node d){
return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x);
}//叉积 如果大于0表示偏左 小于0偏右
ll len(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}//计算两点距离 保证无共线的话可以不写
ll cmp(node a,node b){
ll n=check(t[1],a,t[1],b);
if(n==0)
return len(t[1],a)>len(t[1],b);
if(n>0) return 1;
else return 0;
}//仅用于凸包的极角排序 写死了第一个点作为基准点
ll cmpup(node a,node b){
ll n=check(t[x],a,t[x],b);
if(n==0)
return len(t[x],a)>len(t[x],b);
if(n>0) return 1;
else return 0;
}
ll cmpdown(node a,node b){
ll n=check(t[x],a,t[x],b);
if(n==0)
return len(t[x],a)>len(t[x],b);
if(n>0) return 1;
else return 0;
}
map<ll,map<ll,ll> > mp;
ll sslove(){
ll j=0,q=0;
for(int i=1;i<=n;i++){
if(t[i].y>t[x].y){
sup[j]=t[i];
j++;
}
else if(t[i].y==t[x].y){
if(t[i].x>t[x].x){
sup[j]=t[i];
j++;
}
else if(t[i].x==t[x].x){
continue;
}
else{
sdown[q]=t[i];
q++;
}
}
else{
sdown[q]=t[i];
q++;
}
}//分组,y更大或者x大的在一侧
sort(sup,sup+j,cmpup);
sort(sdown,sdown+q,cmpdown);
ll ans=0;
for(ll i=0;i<j-1;i++){
// printf(" %lld %lld %lld\n",i,sup[i].x,sup[i].y);
if(mp[sup[i].x][sup[i].y]&&mp[sup[i+1].x][sup[i+1].y]) ans++;
}
// printf(" %lld %lld %lld\n",j-1,sup[j-1].x,sup[j-1].y);
for(ll i=0;i<q-1;i++){
// printf(" %lld %lld %lld\n",i,sdown[i].x,sdown[i].y);
if(mp[sdown[i].x][sdown[i].y]&&mp[sdown[i+1].x][sdown[i+1].y]) ans++;
}
// printf(" %lld %lld %lld\n",q-1,sdown[q-1].x,sdown[q-1].y);
if(mp[sup[j-1].x][sup[j-1].y]==1&&mp[sdown[0].x][sdown[0].y]==1) ans++;
if(mp[sup[0].x][sup[0].y]==1&&mp[sdown[q-1].x][sdown[q-1].y]==1) ans++;
// printf("ans=%lld\n\n",ans);
return ans;
}
void slove(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld%lld",&t[i].x,&t[i].y);
}//读取每个点的x,y
for(ll i=2;i<=n;i++){
if((t[i].y<t[1].y)||(t[i].y==t[1].y&&t[i].x<t[1].x)){
ll mid;
mid=t[i].y;
t[i].y=t[1].y;
t[1].y=mid;
mid=t[i].x;
t[i].x=t[1].x;
t[1].x=mid;
}
}//保证第一个点处于左下角,即一定在凸包上
sort(t+2,t+1+n,cmp);
s[1]=t[1];
ll cnt=2;
for(ll i=2;i<=n;i++){
while(cnt>2){
int n=check(s[cnt-2],s[cnt-1],s[cnt-1],t[i]);
if(n<0){
cnt--;
}
else {
break;
}
}
s[cnt]=t[i];
cnt++;
}
for(int i=1;i<cnt;i++){
mp[s[i].x][s[i].y]=1;
}
ll ans=0;
for(int w=1;w<=n;w++){
x=w;
if(mp[t[w].x][t[w].y]) continue;
ans+=sslove();
}
printf("%lld\n",ans+1);
return ;
}
int main(){
int T=1;
// scanf("%d",&d);
while(T--) slove();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7956kb
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: 1ms
memory: 7924kb
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: 1ms
memory: 7868kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7868kb
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: 1ms
memory: 7988kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 496ms
memory: 8208kb
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...
output:
30462
result:
wrong answer 1st numbers differ - expected: '718', found: '30462'