Round G - D (Simple Polygon)
#include <bits/stdc++.h>
using namespace std;
int main () {
int T;
scanf("%d", &T);
for(int tc = 1; tc <= T; tc++) {
int N, A;
scanf("%d %d", &N, &A);
if(A < N-2) {
printf("Case #%d: IMPOSSIBLE\n", tc);
continue;
}
printf("Case #%d: POSSIBLE\n", tc);
if(N%4 == 0) {
vector<pair<long long, long long>> u;
vector<pair<long long, long long>> d;
for(int i = 0; i < (N/2); i++) {
if(i%2 == 0) {
u.push_back(make_pair(i,1));
d.push_back(make_pair(i,0));
}
else {
u.push_back(make_pair(i,2));
d.push_back(make_pair(i,1));
}
}
u[N/2-1].second += A-N+2;
for(int i = 0; i < (N/2); i++)
printf("%lld %lld\n", d[i].first, d[i].second);
for(int i = 0; i < (N/2); i++)
printf("%lld %lld\n", u[(N/2)-1-i].first, u[(N/2)-1-i].second);
}
else if(N%4 == 2) {
vector<pair<long long, long long>> u;
vector<pair<long long, long long>> d;
for(int i = 0; i < (N/2); i++) {
if(i%2 == 0) {
u.push_back(make_pair(i,1000000000-1));
d.push_back(make_pair(i,1000000000-2));
}
else {
u.push_back(make_pair(i,1000000000));
d.push_back(make_pair(i,1000000000-1));
}
}
d[N/2-1].second -= A-N+2;
for(int i = 0; i < (N/2); i++)
printf("%lld %lld\n", d[i].first, d[i].second);
for(int i = 0; i < (N/2); i++)
printf("%lld %lld\n", u[(N/2)-1-i].first, u[(N/2)-1-i].second);
}
else {
vector<pair<long long, long long>> u;
vector<pair<long long, long long>> d;
pair<long long, long long> l = make_pair(A+1-(N-1)/2,1);
for(int i = 0; i < ((N-1)/2); i++) {
if(i%2 == 0) {
u.push_back(make_pair(i,1));
d.push_back(make_pair(i,0));
}
else {
u.push_back(make_pair(i,2));
d.push_back(make_pair(i,1));
}
}
for(int i = 0; i < ((N-1)/2); i++)
printf("%lld %lld\n", d[i].first, d[i].second);
printf("%lld %lld\n", l.first, l.second);
for(int i = (N-3)/2; i >= 0; i--)
printf("%lld %lld\n", u[i].first, u[i].second);
}
}
}
Author And Source
이 문제에 관하여(Round G - D (Simple Polygon)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@amxasm/Google-Kick-Start-2021-Round-G-D-Simple-Polygon저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)