QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21771 | #2838. 2D Geometry | WhybullYMe# | WA | 4ms | 6932kb | C++14 | 1.4kb | 2022-03-08 15:07:26 | 2022-05-08 04:03:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5+10;
mt19937 rndNum(chrono::system_clock::now().time_since_epoch().count());
template<class T>
inline T genRnd(const T &limL,const T &limR){
uniform_int_distribution<T>limLR(limL,limR);
return limLR(rndNum);
}
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],st[maxn];
inline bool cmp(vec x,vec y){
ll det=(x-a[0]).cross(y-a[0]);
return det?det>0:(x-a[0]).norm()<(y-a[0]).norm();
}
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;
st[tp=1]=a[1];
for(ri i=2;i<=n;++i){
if(tp>1&&(a[i]-st[tp-1]).cross(st[tp]-st[tp-1]))ret+=3,tp-=2;
else st[++tp]=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<<=1,a[i].y<<=1;
}
sort(a+1,a+n+1);
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: 2ms
memory: 6932kb
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: -100
Wrong Answer
time: 4ms
memory: 6904kb
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 3 6
result:
wrong answer 21st lines differ - expected: '0', found: '3'