QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482097 | #7667. Crane Balancing | Nahidameow | AC ✓ | 0ms | 4080kb | C++20 | 3.0kb | 2024-07-17 17:12:41 | 2024-07-17 17:12:41 |
Judging History
answer
#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
std::ifstream f(name.c_str());
return f.good();
}
namespace Math{
ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
typedef LD T;
const double eps=1e-8;
int sgn(T x){
if(fabs(x)<eps)return 0;
if(x<0)return -1;
if(x>0)return 1;
return 0;}
bool zro(T x){return fabs(x)<=eps;}
struct vec{
T x,y;
vec(){x=y=0;}
vec(T _x,T _y){x=_x;y=_y;}
vec operator + (vec p){return vec(x+p.x,y+p.y);}
vec operator - (vec p){return vec(x-p.x,y-p.y);}
vec operator * (T p){return vec(x*p,y*p);}
vec operator / (T p){return vec(x/p,y/p);}
T operator * (vec p){return x*p.x+y*p.y;}
T operator & (vec p){return x*p.y-y*p.x;}
T LENGTH(){return x*x+y*y;}
T length(){return sqrt(LENGTH());}
};
vec operator *(T A,vec B){return vec(A*B.x,A*B.y);}
T dot(vec A,vec B){return A*B;}
T cross(vec A,vec B){return A&B;}
T orient(vec A,vec P,vec Q){
return cross(Q-P,A);}
std::pair<vec,T> centr(ve<vec>v){
int L=v.size();
vec c;T S=0;
for(int i=0;i+2<L;i++){
T R=cross(v[i]-v[L-1],v[i+1]-v[L-1]);
c=c+R*(v[i]+v[i+1]+v[L-1]);S+=R;
}
return {c/S/3,fabs(S)/2};
}
void solve(){
//don't forget to open long long
int n;std::cin>>n;
ve<vec>v(n);
T L=1e15,R=-1e15;
for(int i=0;i<n;i++)
std::cin>>v[i].x>>v[i].y;
vec C;T S;auto p=centr(v);
C=p.first;S=p.second;
for(auto &p:v)
if(p.y==0)
L=std::min(L,p.x),
R=std::max(R,p.x);
if(sgn(L-C.x)>0){
T d=(L-C.x)*S/(v[0].x-L),u=(R-C.x)*S/(v[0].x-R);
if(sgn(L-v[0].x)>=0)std::cout<<"unstable\n";
else if(sgn(R-v[0].x)>=0)
std::cout<<ll(floor(d+eps))<<" .. inf\n";
else std::cout<<ll(floor(d+eps))<<" .. "<<ll(ceil(u-eps))<<'\n';
}
else if(sgn(C.x-R)>0){
T d=(C.x-R)*S/(R-v[0].x),u=(C.x-L)*S/(L-v[0].x);
if(sgn(v[0].x-R)>=0)std::cout<<"unstable\n";
else if(sgn(v[0].x-L)>=0)
std::cout<<ll(floor(d+eps))<<" .. inf\n";
else std::cout<<ll(floor(d+eps))<<" .. "<<ll(ceil(u-eps))<<'\n';
}else{
if(sgn(L-v[0].x)>0){
T u=(C.x-L)*S/(L-v[0].x);
std::cout<<"0 .. "<<ll(ceil(u-eps))<<'\n';
}else if(sgn(v[0].x-R)>0){
T u=(R-C.x)*S/(v[0].x-R);
std::cout<<"0 .. "<<ll(ceil(u-eps))<<'\n';
}else std::cout<<"0 .. inf\n";
}
}
int main(){
#ifndef ONLINE_JUDGE
if(!FileIfstream("IO.in")){
freopen("IO.in","w",stdout);
return 0;
}
freopen("IO.in","r",stdin);
freopen("IO.out","w",stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T=1;
//std::cin>>T;
while(T--)solve();
#ifndef ONLINE_JUDGE
std::cerr<<std::fixed<<std::setprecision(10)<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
input:
7 50 50 0 50 0 0 30 0 30 30 40 40 50 40
output:
0 .. 1017
result:
ok single line: '0 .. 1017'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
7 50 50 0 50 0 0 10 0 10 30 20 40 50 40
output:
unstable
result:
ok single line: 'unstable'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 -10 10 -10 0 0 0 0 10
output:
0 .. inf
result:
ok single line: '0 .. inf'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
7 50 30 50 25 30 20 30 0 0 0 0 20 20 20
output:
0 .. 409
result:
ok single line: '0 .. 409'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
7 -50 25 -30 20 -30 0 0 0 0 20 -20 20 -50 30
output:
0 .. 409
result:
ok single line: '0 .. 409'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
8 100 100 100 110 50 110 50 50 0 50 0 0 60 0 60 100
output:
0 .. 2125
result:
ok single line: '0 .. 2125'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
6 10 50 100 50 100 60 0 60 0 0 10 0
output:
unstable
result:
ok single line: 'unstable'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
6 0 60 0 0 10 0 10 50 100 50 100 60
output:
3750 .. inf
result:
ok single line: '3750 .. inf'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
7 -100 100 -10 60 -20 0 0 10 20 0 10 60 100 100
output:
0 .. 1500
result:
ok single line: '0 .. 1500'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
8 50 50 -100 50 -100 40 0 40 0 0 10 0 10 40 50 40
output:
710 .. 1363
result:
ok single line: '710 .. 1363'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
8 -300 500 -100 0 0 200 100 0 300 500 100 200 0 400 -100 200
output:
0 .. 40000
result:
ok single line: '0 .. 40000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
10 -400 800 200 400 100 200 0 400 -100 200 -300 500 -100 0 0 200 100 0 300 500
output:
0 .. 53889
result:
ok single line: '0 .. 53889'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
16 1000 1000 1000 1100 -2000 1100 -2000 1 0 1 0 0 10 0 10 1 100 1 100 0 110 0 110 1 200 1 200 0 210 0 210 1000
output:
2125968 .. 3357736
result:
ok single line: '2125968 .. 3357736'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
60 32 25 29 32 25 25 25 22 22 22 22 25 20 25 20 20 23 17 23 10 16 10 9 10 12 12 14 15 12 17 19 17 15 25 15 20 10 20 7 25 0 20 6 20 5 15 5 11 0 15 0 10 0 5 3 0 7 4 5 7 5 10 12 7 10 4 11 2 12 0 15 0 15 3 13 3 13 7 17 7 20 3 20 2 20 0 25 3 30 0 30 3 30 5 27 5 24 7 24 12 27 12 27 9 30 9 30 13 30 16 27 1...
output:
0 .. 2911
result:
ok single line: '0 .. 2911'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
62 32 25 29 32 25 25 25 22 22 22 22 25 20 25 20 20 23 17 23 10 16 10 9 10 12 12 14 12 12 17 19 17 15 25 15 20 10 20 7 25 0 20 6 20 5 15 5 11 0 15 -100 15 -100 10 0 10 0 5 3 0 7 4 5 7 5 10 12 7 10 4 11 2 12 0 15 0 15 3 13 3 13 7 17 7 20 3 20 2 20 0 25 3 30 0 30 3 30 5 27 5 24 7 24 12 27 12 27 9 30 9 ...
output:
735 .. 22911
result:
ok single line: '735 .. 22911'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
62 -100 10 0 10 0 5 3 0 7 4 5 7 5 10 12 7 10 4 11 2 12 0 15 0 15 3 13 3 13 7 17 7 20 3 20 2 20 0 25 3 30 0 30 3 30 5 27 5 24 7 24 12 27 12 27 9 30 9 30 13 30 16 27 16 27 14 25 14 25 17 25 19 32 25 29 32 25 25 25 22 22 22 22 25 20 25 20 20 23 17 23 10 16 10 9 10 12 12 14 12 12 17 19 17 15 25 15 20 10...
output:
unstable
result:
ok single line: 'unstable'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
62 -10 10 0 10 0 5 3 0 7 4 5 7 5 10 12 7 10 4 11 2 12 0 15 0 15 3 13 3 13 7 17 7 20 3 20 2 20 0 25 3 30 0 30 3 30 5 27 5 24 7 24 12 27 12 27 9 30 9 30 13 30 16 27 16 27 14 25 14 25 17 25 19 32 25 29 32 25 25 25 22 22 22 22 25 20 25 20 20 23 17 23 10 16 10 9 10 12 12 14 11 12 17 19 17 15 25 15 20 10 ...
output:
0 .. 368
result:
ok single line: '0 .. 368'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
12 11 4 11 5 7 5 7 9 6 9 6 5 2 5 2 4 6 4 6 0 7 0 7 4
output:
0 .. 3
result:
ok single line: '0 .. 3'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
12 11 4 11 5 7 5 7 9 6 9 6 5 2 5 2 1 6 1 6 0 7 0 7 4
output:
3 .. 12
result:
ok single line: '3 .. 12'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
7 1500 100 0 1 -2000 100 -1 1 -1 0 1 0 1 1
output:
5 .. 6
result:
ok single line: '5 .. 6'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
100 21 18 18 18 18 16 16 16 15 15 17 15 16 13 13 13 13 15 15 17 15 18 12 18 12 16 11 14 11 10 7 10 7 13 5 15 7 18 4 18 3 16 3 14 0 8 1 8 1 3 0 1 0 0 1 0 1 1 2 2 3 2 2 1 2 0 3 1 4 2 4 3 3 4 3 3 2 3 2 5 4 5 5 4 5 3 6 2 5 1 5 0 8 0 7 1 7 2 8 3 7 4 6 4 7 5 7 6 8 6 8 5 9 5 10 6 10 4 9 3 10 2 9 1 10 0 11 ...
output:
0 .. 2018
result:
ok single line: '0 .. 2018'