QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482097#7667. Crane BalancingNahidameowAC ✓0ms4080kbC++203.0kb2024-07-17 17:12:412024-07-17 17:12:41

Judging History

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

  • [2024-07-17 17:12:41]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4080kb
  • [2024-07-17 17:12:41]
  • 提交

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'