QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102799 | #6374. LaLa and Magic Circle (LiLi Version) | applese | WA | 30ms | 5232kb | C++14 | 1.7kb | 2023-05-03 17:58:35 | 2023-05-03 17:58:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
}p[1005];
int n = 1000;
vector<pair<Point, Point> > ans;
long long Cross(Point a, Point b) {
return 1ll * a.x * b.y - 1ll * b.y * a.x;
}
int Check(int l, int r) {
for(int i = 0; i < n; ++ i) {
if(Cross(p[i] - p[l], p[r] - p[l]) > 0)
return 0;
}
return 1;
}
int main() {
p[0] = Point(0, 0);
for(int i = 1; i < n / 2; ++ i) {
p[i] = p[i - 1] + Point(i, i * i);
}
for(int i = n / 2; i < n; ++ i) {
if(i & 1)
p[i] = p[i - 1] + Point(n / 2, n / 2 * n / 2);
else
p[i] = p[i - 1] + Point(1, 0);
}
printf("%d\n", n);
for(int i = 0; i < n; ++ i)
printf("%d %d\n", p[i].x, p[i].y);
for(int j = n / 2 - 2; j >= 0; -- j) {
if(!p[j + 2].y)
continue;
ans.push_back({p[j], p[j + 2]});
// assert(Check(j, j + 2));
p[j + 1] = p[j + 2] + p[j] - p[j + 1];
}
for(int i = n / 2 + 2, k = n / 2; i < n; i += 2, ++ k) {
ans.push_back({p[k], p[i]});
// assert(Check(k, i));
for(int j = i - 1; j > k; -- j)
p[j] = p[i] + p[k] - p[j];
reverse(p + k + 1, p + i);
// for(int l = k + 1, r = i - 1; l < r; ++ l, -- r)
// swap(p[l], p[r]);
for(int j = k - 1; j >= 0; -- j) {
if(!p[j + 2].y)
continue;
ans.push_back({p[j], p[j + 2]});
// assert(Check(j, j + 2));
p[j + 1] = p[j + 2] + p[j] - p[j + 1];
}
}
printf("%d\n", (int)ans.size());
for(auto p : ans)
printf("%d %d %d %d\n", p.first.x, p.first.y, p.second.x, p.second.y);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 30ms
memory: 5232kb
input:
output:
1000 0 0 1 1 3 5 6 14 10 30 15 55 21 91 28 140 36 204 45 285 55 385 66 506 78 650 91 819 105 1015 120 1240 136 1496 153 1785 171 2109 190 2470 210 2870 231 3311 253 3795 276 4324 300 4900 325 5525 351 6201 378 6930 406 7714 435 8555 465 9455 496 10416 528 11440 561 12529 595 13685 630 14910 666 1620...
result:
wrong answer Both p and q must be on the boundary of the convex hull