QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21781 | #2838. 2D Geometry | WhybullYMe# | WA | 4ms | 7388kb | C++14 | 1.2kb | 2022-03-08 15:20:21 | 2022-05-08 04:03:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=2e5+10;
inline ll sqr(ll k){return k*k;}
struct vec{
ll x,y;
inline vec(ll x_=0,ll y_=0):x(x_),y(y_){}
inline vec operator-(const vec &k){
return vec(x-k.x,y-k.y);
}
inline bool operator<(const vec &k)const{
return x!=k.x?x<k.x:y<k.y;
}
inline ll cross(const vec &k){
return x*k.y-y*k.x;
}
inline ll norm(){
return x*x+y*y;
}
inline ll dist(const vec &k){
return sqrt(sqr(x-k.x)+sqr(y-k.y));
}
}a[maxn];
inline bool cmp(vec x,vec y){
x=x-a[0],y=y-a[0];
double tx=atan2(x.y,x.x),ty=atan2(y.y,y.x);
return tx!=ty?tx<ty:x.x<y.x;
}
int n,tp;
inline int graham(){
vec tmp=a[1];
for(ri i=1;i<n;++i)a[i]=a[i+1];
a[n]=tmp;
int ret=0;
deque<vec>st;
for(ri i=1;i<=n;++i){
if(st.size()>1&&(a[i]-st.front()).cross(st.back()-st.front()))ret+=3,st.pop_front(),st.pop_back();
else st.push_back(a[i]);
}
return ret;
}
int main(){
while(~scanf("%d",&n)){
a[0]={0,0};
for(ri i=1;i<=n;++i){
scanf("%lld%lld",&a[i].x,&a[i].y);
a[0].x+=a[i].x,a[0].y+=a[i].y;
a[i].x*=n,a[i].y*=n;
}
sort(a+1,a+n+1,cmp);
printf("%d\n",n-max({graham(),graham(),graham()}));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7388kb
input:
3 0 0 0 1 0 2 3 0 0 0 1 1 0 6 0 0 0 1 0 2 0 3 1 1 1 2
output:
3 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 7152kb
input:
1 0 0 2 0 0 1 1 3 0 0 0 1 0 2 3 0 0 0 1 1 0 4 3 0 0 2 3 3 3 1 4 2 3 1 1 0 3 0 2 4 0 0 0 3 0 2 0 1 5 8 6 9 2 2 3 7 4 1 5 5 2 2 4 2 6 2 7 2 0 4 5 3 7 5 4 4 4 9 4 9 9 5 5 4 5 9 5 5 4 3 1 0 5 3 2 1 2 7 2 6 2 5 2 6 7 2 7 9 0 3 8 8 4 4 3 8 6 2 8 2 5 3 5 3 8 2 0 0 2 6 2 3 8 4 2 9 2 2 2 6 4 9 6 2 1 7 6 6 5 ...
output:
1 2 3 0 1 1 4 2 2 2 2 5 0 0 0 0 0 0 0 3 0 6
result:
ok 22 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 7260kb
input:
7 0 1 0 0 7 7 6 2 6 9 4 4 3 5 7 3 7 3 2 9 1 0 6 1 8 5 0 9 5 7 3 7 2 3 4 5 6 7 7 7 5 8 4 7 7 1 6 5 7 7 2 3 5 0 8 8 8 3 8 7 1 8 3 4 8 8 1 9 7 8 1 7 0 0 7 6 9 2 7 4 5 2 1 4 6 2 3 7 6 7 3 1 1 9 5 7 6 6 5 2 5 1 5 3 7 6 4 1 6 7 3 5 4 2 3 0 0 3 2 7 2 9 4 9 8 9 8 0 1 7 2 6 6 2 7 3 5 4 0 4 1 4 3 0 8 4 7 4 6 ...
output:
1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1
result:
ok 21 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 7192kb
input:
8 3 2 4 4 3 9 7 9 9 3 9 1 4 2 5 3 8 0 6 0 2 1 6 9 9 5 5 8 4 6 8 0 9 8 1 8 8 1 9 0 1 3 6 4 3 6 4 0 1 6 8 5 3 1 0 0 1 7 1 3 7 8 8 6 4 6 2 8 3 3 7 8 0 8 6 3 0 4 2 3 5 3 5 4 8 6 2 9 7 3 2 6 5 2 2 1 5 4 7 2 5 8 1 1 1 0 1 5 2 8 8 9 8 8 0 0 1 4 8 8 0 3 3 8 2 5 5 3 0 0 0 6 2 8 9 8 3 9 3 5 3 1 6 5 6 2 1 1 8 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
result:
ok 57 lines
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 7236kb
input:
9 14 16 8 14 18 19 0 10 5 9 0 5 1 2 12 9 15 11 9 16 12 3 9 10 14 17 14 6 10 2 19 17 17 0 13 7 2 9 17 1 14 13 5 14 9 2 13 0 1 18 17 13 11 3 5 13 9 13 0 13 3 5 4 6 14 3 5 17 14 5 17 19 17 5 6 9 3 18 18 9 14 14 6 4 17 10 16 15 8 14 10 14 18 16 9 17 10 19 19 1 16 18 17 9 13 10 15 19 3 6 16 17 16 9 13 2 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 22nd lines differ - expected: '0', found: '3'