QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768646 | #6375. LaLa and Magic Circle (LaLa Version) | ekkxjewj | WA | 1ms | 8372kb | C++14 | 3.0kb | 2024-11-21 13:15:45 | 2024-11-21 13:15:45 |
Judging History
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'