QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102799#6374. LaLa and Magic Circle (LiLi Version)appleseWA 30ms5232kbC++141.7kb2023-05-03 17:58:352023-05-03 17:58:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 17:58:36]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:5232kb
  • [2023-05-03 17:58:35]
  • 提交

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