QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562399#181. Skinny PolygonPetroTarnavskyi#AC ✓60ms3816kbC++201.6kb2024-09-13 17:20:042024-09-13 17:20:05

Judging History

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

  • [2024-09-13 17:20:05]
  • 评测
  • 测评结果:AC
  • 用时:60ms
  • 内存:3816kb
  • [2024-09-13 17:20:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

tuple<LL, LL, LL> gcdExt(LL a, LL b)
{
	LL x1 = 1, y1 = 0;
	LL x2 = 0, y2 = 1;
	while (b)
	{
		LL k = a / b;
		x1 -= k * x2;
		y1 -= k * y2;
		a %= b;
		swap(a, b);
		swap(x1, x2);
		swap(y1, y2);
	}
	return {a, x1, y1};
}

struct Pt
{
	LL x, y;
	Pt operator-(const Pt& p)
	{
		return {x - p.x, y - p.y};
	}
};

LL cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}

LL areaPolygon(const vector<Pt>& v)
{
	LL area = 0;
	int n = SZ(v);
	FOR(i, 0, n)
		area += cross(v[i], v[(i + 1) % n]);
	return area;
}

void solve()
{
	LL xbb, ybb;
	cin >> xbb >> ybb;
	auto [g, y, x] = gcdExt(xbb, ybb);
	vector<Pt> ans;
	if (g <= 50000)
	{
		while (y <= 0)
		{
			y += ybb / g;
			x -= xbb / g;
		}
		x *= -1;
		assert(0 <= x && x <= xbb && 0 <= y && y <= ybb);
		ans = {{0, 0}, {xbb, ybb}, {x, y}};
	}
	else
		ans = {{0, 0}, {xbb, ybb - 1}, {xbb / g, ybb / g}, {xbb - 1, ybb}};
	LL area = areaPolygon(ans);
	assert(0 <= area && area <= 50000);
	cout << SZ(ans) << "\n";
	for (const Pt& p : ans)
		cout << p.x << " " << p.y << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	while (n--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
208580387 17780549

output:

3
0 0
208580387 17780549
71813922 6121817

result:

ok  (1 test case)

Test #2:

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

input:

333
155914131 107580856
118325725 433000045
150924234 839090962
767758071 151584835
935957277 433955814
255598858 389742335
743573833 322900708
177444310 470011898
379176898 383413750
290074146 970040537
523602397 927219136
645587146 25000397
627968056 634567884
212268328 383837986
263720310 7876452...

output:

3
0 0
155914131 107580856
119773823 82644019
3
0 0
118325725 433000045
18064551 66105248
3
0 0
150924234 839090962
22937533 127525422
3
0 0
767758071 151584835
649204244 128177771
3
0 0
935957277 433955814
289529821 134240261
3
0 0
255598858 389742335
81275249 123930152
3
0 0
743573833 322900708
212...

result:

ok  (333 test cases)

Test #3:

score: 0
Accepted
time: 56ms
memory: 3788kb

input:

100000
445582530 822667069
295137536 241061329
670267416 776556030
871367439 81023454
454423135 366064128
736723929 790460100
182875860 204292390
574918465 345805718
493866571 723390727
805418859 189693014
58919937 642107187
539263399 413002313
496600036 183840910
713714270 7507250
613836159 4867129...

output:

3
0 0
445582530 822667069
118945871 219606570
3
0 0
295137536 241061329
8094671 6611535
3
0 0
670267416 776556030
89774527 104010651
3
0 0
871367439 81023454
255204179 23729971
3
0 0
454423135 366064128
25486178 20530591
3
0 0
736723929 790460100
6183767 6634807
3
0 0
182875860 204292390
905015 1011...

result:

ok  (100000 test cases)

Test #4:

score: 0
Accepted
time: 57ms
memory: 3816kb

input:

100000
40764710 571268444
644533103 547148435
72380682 694505998
492672851 500925067
916128611 61300316
461036435 738009339
616271084 695824755
378717848 980922355
874971482 539592849
184631559 170542854
37025871 855596918
629940618 398276421
473246454 792463592
673461967 138691078
309615971 5797594...

output:

3
0 0
40764710 571268444
11663842 163454735
3
0 0
644533103 547148435
514278300 436574267
3
0 0
72380682 694505998
12753358 122370823
3
0 0
492672851 500925067
143379271 145780858
3
0 0
916128611 61300316
70188346 4696467
3
0 0
461036435 738009339
412928251 660999614
3
0 0
616271084 695824755
316754...

result:

ok  (100000 test cases)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

5
629048520 954056922
991237288 394814852
933314220 414806320
977531956 696227796
128059380 992460195

output:

4
0 0
629048520 954056921
60 91
629048519 954056922
4
0 0
991237288 394814851
118 47
991237287 394814852
4
0 0
933314220 414806319
9 4
933314219 414806320
4
0 0
977531956 696227795
139 99
977531955 696227796
4
0 0
128059380 992460194
4 31
128059379 992460195

result:

ok  (5 test cases)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

135
909194160 584481960
565795152 911558856
568913561 980885450
573603600 979906150
902008364 290970440
990265276 353666170
164983208 926444168
955917600 21725400
917259714 131037102
932912340 435359092
873834958 925672625
956908140 956908140
959558640 671691048
139078870 943749475
902782638 5517005...

output:

4
0 0
909194160 584481959
14 9
909194159 584481960
4
0 0
565795152 911558855
18 29
565795151 911558856
4
0 0
568913561 980885449
29 50
568913560 980885450
4
0 0
573603600 979906149
24 41
573603599 979906150
4
0 0
902008364 290970439
31 10
902008363 290970440
4
0 0
990265276 353666169
14 5
990265275 ...

result:

ok  (135 test cases)

Test #7:

score: 0
Accepted
time: 57ms
memory: 3652kb

input:

100000
978598980 260959728
244699944 932505192
969301948 357111244
929462272 666406912
901656183 429584883
429662040 966739590
681572528 973675040
164010525 940327010
947363060 328676980
964217320 48210866
932539188 699404391
492333782 984667564
361531998 990865476
102908007 983343178
427242866 9539...

output:

4
0 0
978598980 260959727
15 4
978598979 260959728
4
0 0
244699944 932505191
37 141
244699943 932505192
4
0 0
969301948 357111243
19 7
969301947 357111244
4
0 0
929462272 666406911
53 38
929462271 666406912
4
0 0
901656183 429584882
191 91
901656182 429584883
4
0 0
429662040 966739589
4 9
429662039 ...

result:

ok  (100000 test cases)

Test #8:

score: 0
Accepted
time: 60ms
memory: 3816kb

input:

100000
340909556 944057232
330324334 990973002
768878057 995018662
612231795 925150268
279385585 949910989
642134412 980099892
922970304 836441838
964618630 653451330
941189762 952133829
616528991 901080833
923249010 307749670
954323856 656097651
949943722 149991114
808177862 977331368
988742625 700...

output:

4
0 0
340909556 944057231
13 36
340909555 944057232
4
0 0
330324334 990973001
1 3
330324333 990973002
4
0 0
768878057 995018661
17 22
768878056 995018662
4
0 0
612231795 925150267
45 68
612231794 925150268
4
0 0
279385585 949910988
5 17
279385584 949910989
4
0 0
642134412 980099891
19 29
642134411 9...

result:

ok  (100000 test cases)

Test #9:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

2
987319238 3
4 969079019

output:

3
0 0
987319238 3
658212825 2
3
0 0
4 969079019
1 242269755

result:

ok  (2 test cases)

Test #10:

score: 0
Accepted
time: 43ms
memory: 3656kb

input:

99999
43280 18478
904953576 4
63826 20961
4 926615536
3 931592998
2 943853231
96239 13455
39315 48605
3 969620891
53642 6145
90277 97911
966250909 3
147 461
8555 27851
93 122
4 979241063
12276 75211
38547 75793
3 988689525
999885543 2
896 18282
3 942876530
951116180 3
88480 53927
189 251
339 434
436...

output:

3
0 0
43280 18478
10601 4526
3
0 0
904953576 4
226238393 1
3
0 0
63826 20961
16921 5557
3
0 0
4 926615536
0 1
3
0 0
3 931592998
2 621061999
3
0 0
2 943853231
1 471926616
3
0 0
96239 13455
3233 452
3
0 0
39315 48605
2171 2684
3
0 0
3 969620891
1 323206964
3
0 0
53642 6145
2645 303
3
0 0
90277 97911
2...

result:

ok  (99999 test cases)

Test #11:

score: 0
Accepted
time: 47ms
memory: 3816kb

input:

100000
4 902697494
993602441 4
929693256 4
4 935130618
87306 2444
68 184
4 935698855
64827 97627
474 145
978453337 4
8246 57921
6019 78972
2560 55490
311 120
938948062 4
405 461
4 952390731
955084608 2
2 933877275
991376723 4
3 964361663
4 971255311
3 910910052
112 210
54400 60960
921019617 3
303 14...

output:

3
0 0
4 902697494
1 225674374
3
0 0
993602441 4
248400610 1
3
0 0
929693256 4
232423313 1
3
0 0
4 935130618
1 233782655
3
0 0
87306 2444
5537 155
3
0 0
68 184
7 19
3
0 0
4 935698855
1 233924714
3
0 0
64827 97627
58034 87397
3
0 0
474 145
389 119
3
0 0
978453337 4
244613334 1
3
0 0
8246 57921
7583 53...

result:

ok  (100000 test cases)

Test #12:

score: 0
Accepted
time: 44ms
memory: 3744kb

input:

100000
70201 35342
49822 31446
19302 72849
2 958622727
951309038 4
2 919851873
906487676 2
4 918079296
55781 32958
131 445
920225892 4
429 14
4 956168370
82907 24874
89452 70422
28651 64539
88008 81641
960089256 2
992834307 4
379 87
76008 2908
925297063 3
76204 73584
987267493 2
2 955583802
93671310...

output:

3
0 0
70201 35342
60899 30659
3
0 0
49822 31446
9709 6128
3
0 0
19302 72849
1293 4880
3
0 0
2 958622727
1 479311364
3
0 0
951309038 4
237827259 1
3
0 0
2 919851873
1 459925937
3
0 0
906487676 2
453243837 1
3
0 0
4 918079296
0 1
3
0 0
55781 32958
23182 13697
3
0 0
131 445
68 231
3
0 0
920225892 4
230...

result:

ok  (100000 test cases)