QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768646#6375. LaLa and Magic Circle (LaLa Version)ekkxjewjWA 1ms8372kbC++143.0kb2024-11-21 13:15:452024-11-21 13:15:45

Judging History

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

  • [2024-11-21 13:15:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8372kb
  • [2024-11-21 13:15:45]
  • 提交

answer

#pragma warning(disable:4996)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;



#define M_PI 3.14159265358979323846
#define EP 0.0000000000001

struct MathVector
{
	ll x, y;
	ld angle;
	MathVector() {}
	MathVector(ld _x, ld _y) : x(_x), y(_y)
	{
		ld angleInRadians = std::atan2(y, x);

		if (angleInRadians < 0) {
			angleInRadians += 2 * M_PI;
		}

		angle = angleInRadians * (180.0 / M_PI);
	}
	bool operator<(const MathVector& other) const {
		return angle < other.angle;
	}

	void angleEdit(ld angleStd)
	{
		angle -= angleStd;
		if (angle < 0) angle += 360.0;
	}
};


int n;
pair<ll, ll> points[101000];
MathVector vecs[101000];

int ans;
pair<ll, ll> ansList[100100];

pair<ll, ll> operator+(const pair<ll, ll>& p1, const pair<ll, ll>& p2) {
	return { p1.first + p2.first, p1.second + p2.second };
}

pair<ll, ll> operator-(const pair<ll, ll>& p1, const pair<ll, ll>& p2) {
	return { p1.first - p2.first, p1.second - p2.second };
}
bool operator<(const pair<ll, ll>& p1, const pair<ll, ll>& p2) {
	if (p1.first == p2.first)
		return p1.second < p2.second;
	return p1.first < p2.first;
}

inline int CCW(MathVector p1, MathVector p2, MathVector p3)
{

	ll res = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
	if (res < 0)
		return -1;
	else if (res > 0)
		return 1;
	else
		return 0;
}

int main()
{
	pair<ll, ll> curPoints = { 400000,400000 }, leftBottom = {400000,400000};
	int leftBottomIdx = -1;
	scanf("%d", &n);

	int startIdx = -1;

	for (int i = 0; i < n; i++)
	{
		scanf("%lld %lld", &points[i].first, &points[i].second);
		if (i > 0)
			vecs[i] = MathVector(points[i].first - points[i - 1].first, points[i].second - points[i - 1].second);

		if (points[i] < curPoints)
		{
			curPoints = points[i];
			startIdx = i;
		}
	}
	vecs[0] = MathVector(points[0].first - points[n - 1].first, points[0].second - points[n - 1].second);

	ld angleStd = vecs[(startIdx + 1) % n].angle;


	for (int i = 0; i < n; i++)
		vecs[i].angleEdit(angleStd);

	sort(vecs, vecs + n);

	//printf("%lld %lld", curPoints.first, curPoints.second);
	ansList[ans++] = curPoints;
	leftBottom = curPoints;
	leftBottomIdx = 0;

	for (int i = 0; i < n; i++)
	{
		if (i > 0 && abs(vecs[i].angle - vecs[i - 1].angle) > EP)
		{
			if (leftBottom.first > curPoints.first ||
				(leftBottom.first == curPoints.first && leftBottom.second > curPoints.second))
			{
				leftBottom = curPoints;
				leftBottomIdx = ans;
			}
			ansList[ans++] = curPoints;
		}
		curPoints.first += vecs[i].x;
		curPoints.second += vecs[i].y;

	}
	//if (abs(vecs[0].angle - vecs[n - 1].angle) > EP)
		//ansList[ans++] = curPoints;

	printf("%d\n", ans);
	for (int i = leftBottomIdx; i < ans; i++)
		printf("%lld %lld\n", ansList[i].first, ansList[i].second);
	for (int i = 0; i < leftBottomIdx; i++)
		printf("%lld %lld\n", ansList[i].first, ansList[i].second);

	return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8
1 0
4 0
6 0
3 1
5 2
2 1
6 3
0 2

output:

6
0 2
1 0
6 0
12 3
9 4
3 3

result:

ok 13 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 8344kb

input:

3
3 1
5 0
0 3

output:

3
0 3
3 1
5 0

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8344kb

input:

3
0 2
5 10
3 8

output:

3
0 2
5 10
3 8

result:

ok 7 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 6212kb

input:

3
9 8
6 6
7 3

output:

3
6 6
7 3
9 8

result:

ok 7 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 6256kb

input:

4
5 0
5 1
0 3
3 1

output:

4
0 3
3 1
5 0
5 1

result:

ok 9 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 8252kb

input:

4
5 10
3 8
0 2
10 9

output:

4
0 2
10 9
5 10
3 8

result:

ok 9 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 8236kb

input:

4
7 3
6 6
9 8
0 3

output:

4
0 3
7 3
10 5
9 8

result:

ok 9 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 8360kb

input:

5
0 3
0 0
5 0
5 1
3 1

output:

5
0 0
5 0
5 1
2 3
0 3

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 6388kb

input:

5
5 10
3 8
1 6
0 2
10 9

output:

4
0 2
10 9
5 10
1 6

result:

ok 9 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 8372kb

input:

5
9 8
8 8
0 3
7 3
6 6

output:

5
0 3
7 3
10 5
9 8
8 8

result:

ok 11 numbers

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 8248kb

input:

6
5 0
9 1
0 3
0 0
3 1
5 1

output:

5
-6 -1
-4 -1
0 0
3 1
-6 3

result:

wrong answer 2nd numbers differ - expected: '0', found: '-6'