QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562399 | #181. Skinny Polygon | PetroTarnavskyi# | AC ✓ | 60ms | 3816kb | C++20 | 1.6kb | 2024-09-13 17:20:04 | 2024-09-13 17:20:05 |
Judging History
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)