QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#758154#7667. Crane Balancingrlc202204WA 0ms3948kbC++172.8kb2024-11-17 16:13:502024-11-17 16:13:55

Judging History

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

  • [2024-11-17 16:13:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3948kb
  • [2024-11-17 16:13:50]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;

struct Vec {
	double x, y;
	Vec (double _x = 0, double _y = 0) :
		x(_x), y(_y) {}
};
Vec operator+(Vec a, Vec b) {
	return Vec(a.x + b.x, a.y + b.y);
}
Vec operator-(Vec a, Vec b) {
	return Vec(a.x - b.x, a.y - b.y);
}
double operator*(Vec a, Vec b) {
	return a.x * b.y - a.y * b.x;
}

int n;
Vec p[N];

double S;//多边形面积
Vec G;//多边形重心

Vec calc(Vec a, Vec b, Vec c) {
	//a, b, c 三角形的重心
	return Vec((a.x + b.x + c.x) / 3, (a.y + b.y + c.y) / 3); 
}

void init() {
	Vec o = Vec(0, 0);
	S = 0;
	G = Vec(0, 0);
	for (int i = 1; i <= n; i++) {
		double st = p[i] * p[i % n + 1] / 2;
		Vec gt = calc(o, p[i], p[i % n + 1]);
	//	cout << i << " " << gt.x << " " << gt.y << endl;
		S += st;
		G = G + Vec(st * gt.x, st * gt.y);
	}
	G.x /= S, G.y /= S;
}

const double eps = 1e-8;

int myfloor(double x) {
//	return (int)floor(x);
	int ans = floor(x);
	if (abs(ans + 1 - x) <= eps)
		ans++;
	return ans;
}
int myceil(double x) {
//	return (int)ceil(x);
	int ans = myfloor(x);
	if (abs(ans - x) > eps)
		ans++;
	return ans;
}



int main() {
	scanf("%d", &n);
	int L = 2e9, R = -2e9;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		p[i] = Vec(x, y);
		if (y == 0) {
			L = min(x, L);
			R = max(x, R);
		}
	}
	//求出多边形的重心和面积 
	init();
	S = abs(S);
//	cout << G.x << " " << G.y << " " << S << " " << L << " " << R << endl;
	
//	cout << (1017 * p[1].x + S * G.x) / (1017 + S) << endl;
	
	if (L <= G.x && G.x <= R) {
		if (L <= p[1].x && p[1].x <= R) {
			printf("0 .. inf\n");
		}
		else if (p[1].x < L) {
			int mxw = myceil(S * (G.x - L) / (L - p[1].x));
			printf("0 .. %d\n", mxw); 
		}
		else {
			int mxw = myceil(S * (G.x - R) / (R - p[1].x));
			printf("0 .. %d\n", mxw);
		}
	}
	else if (G.x < L) {
		if (L <= p[1].x && p[1].x <= R) {
			int mnw = myfloor(S * (G.x - L) / (L - p[1].x));
			printf("%d .. inf\n", mnw);
		}
		else if (p[1].x < L) {
			printf("unstable\n"); 
		}
		else {
			double mnw = S * (G.x - L) / (L - p[1].x);
			double mxw = S * (G.x - R) / (R - p[1].x);
			if (mnw <= mxw)
				printf("%d .. %d\n", myfloor(mnw), myceil(mxw));
			else
				printf("unstable\n");
		}
	}
	else {
		if (L <= p[1].x && p[1].x <= R) {
			int mnw = myfloor(S * (G.x - R) / (R - p[1].x));
			printf("%d .. inf\n", mnw);
		}
		else if (p[1].x > R) {
			printf("unstable\n"); 
		}
		else {
			double mnw = S * (G.x - R) / (R - p[1].x);
			double mxw = S * (G.x - L) / (L - p[1].x);
			if (mnw <= mxw)
				printf("%d .. %d\n", myfloor(mnw), myceil(mxw));
			else
				printf("unstable\n");
		}
	}
	return 0;
} 
 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

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: 3668kb

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: 3888kb

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: 3948kb

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: 3800kb

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: 3880kb

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: -100
Wrong Answer
time: 0ms
memory: 3872kb

input:

6
10 50
100 50
100 60
0 60
0 0
10 0

output:

-2147483648 .. inf

result:

wrong answer 1st lines differ - expected: 'unstable', found: '-2147483648 .. inf'