QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482082#7667. Crane BalancingNahidameowWA 1ms3996kbC++203.0kb2024-07-17 17:08:392024-07-17 17:08:40

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 17:08:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3996kb
  • [2024-07-17 17:08:39]
  • 提交

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'