QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482082 | #7667. Crane Balancing | Nahidameow | WA | 1ms | 3996kb | C++20 | 3.0kb | 2024-07-17 17:08:39 | 2024-07-17 17:08:40 |
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 double 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: 3776kb
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: 3788kb
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: 1ms
memory: 3940kb
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: 3772kb
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: 3996kb
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: -100
Wrong Answer
time: 0ms
memory: 3864kb
input:
8 100 100 100 110 50 110 50 50 0 50 0 0 60 0 60 100
output:
0 .. 2126
result:
wrong answer 1st lines differ - expected: '0 .. 2125', found: '0 .. 2126'