#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
using namespace std;
static void check(bool cond, string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
check(!build_called, "build is called more than once");
build_called = true;
m = u.size();
check(int(v.size()) == m, "u.size() != v.size()");
check(int(a.size()) == m, "u.size() != a.size()");
check(int(b.size()) == m, "u.size() != b.size()");
_u = u;
_v = v;
_a = a;
_b = b;
}
#include "parks.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
//typedef long double ld;
typedef long long ll;
using namespace std;
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}
struct seg{
int l,r,id;
};
const string out[2]={"NO\n","YES\n"};
const ll dx[]={-1,-1,1,1};
const ll dy[]={-1,1,-1,1};
const ll dxx[]={0,0,2,-2};
const ll dyy[]={2,-2,0,0};
const int md=998244353;
const int mod=1e9+7;
const int mx=8e5+12;
const int tst=1e5;
const bool T=0;
pair<int,pair<int,int>> p[mx];
map<int,bool> used[mx];
map<int,int> pos[mx];
vector<int> g[mx];
int ma[mx];
int mi[mx];
int d[mx];
void dfs(int x,int y){
used[x][y]=1;
ma[x]=max(ma[x],y);
mi[x]=min(mi[x],y);
for(int k=0;k<4;k++){
int x1=x+dxx[k];
int y1=y+dyy[k];
if(!used[x1].count(y1) && pos[x1].count(y1))dfs(x1,y1);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
if(n==1){
build({},{},{},{});
return 1;
}
for(int i=1;i<=n;i++){
p[i]={x[i-1],{y[i-1],i}};
d[i]=i;
}
sort(p+1,p+n+1);
int mx=0;
reverse(x.begin(),x.end());
reverse(y.begin(),y.end());
x.push_back(0);
y.push_back(0);
reverse(x.begin(),x.end());
reverse(y.begin(),y.end());
for(int i=1;i<=n;i++){
mx=max(mx,x[i]);
pos[x[i]][y[i]]=i-1;
}
srand(time(0));
for(int i=0;i<=mx;i++)mi[i]=1e9;
dfs(x[1],y[1]);
for(int i=1;i<=n;i++){
if(!used[x[i]][y[i]]){
return 0;
}
}
vector<int> u,v,a,b;
if(mx==2){
for(int i=mi[2];i<ma[2];i+=2){
u.push_back(pos[2][i]);
v.push_back(pos[2][i+2]);
a.push_back(1);
b.push_back(i+1);
}
build(u,v,a,b);
return 1;
}
if(mx==4){
if(!ma[2]){
for(int i=mi[4];i<ma[4];i+=2){
u.push_back(pos[4][i]);
v.push_back(pos[4][i+2]);
a.push_back(3);
b.push_back(i+1);
}
build(u,v,a,b);
return 1;
}
for(int i=1;i<=n;i++){
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
if(x[i]==2)a.push_back(1);
else a.push_back(5);
b.push_back(y[i]+1);
}
}
for(int i=1;i<=n;i++){
if(x[i]!=2)continue;
if(pos[4].count(y[i])){
u.push_back(i-1);
v.push_back(pos[4][y[i]]);
a.push_back(3);
b.push_back(y[i]-1);
}
}
build(u,v,a,b);
return 1;
}
bool ok=0;
random_shuffle(d+1,d+n+1);
for(int i=1;i<=n;i++){
int xx=i;
i=d[i];
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
a.push_back(x[i]+1);
}
else if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1];
a.push_back(x[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
i=xx;
}
if(u.size()>0){
build(u,v,a,b);
return 1;
}
random_shuffle(d+1,d+n+1);
for(int i=0;i<=mx;i++)used[i].clear();
for(int i=1;i<=n;i++){
int xx=i;
i=d[i];
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1]=1;
a.push_back(x[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1];
a.push_back(x[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
xx=i;
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
random_shuffle(d+1,d+n+1);
for(int i=1;i<=n;i++){
int xx=i;
i=d[i];
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
a.push_back(x[i]+1);
}
else if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1];
a.push_back(x[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
i=xx;
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
random_shuffle(d+1,d+n+1);
for(int i=1;i<=n;i++){
int xx=i;
i=d[i];
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1]=1;
a.push_back(x[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1];
a.push_back(x[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
i=xx;
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
for(int i=1;i<=n;i++){
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
a.push_back(x[i]+1);
}
else if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1];
a.push_back(x[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
}
if(u.size()>0){
build(u,v,a,b);
return 1;
}
for(int i=0;i<=mx;i++)used[i].clear();
for(int i=1;i<=n;i++){
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1]=1;
a.push_back(x[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1];
a.push_back(x[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
for(int i=1;i<=n;i++){
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
a.push_back(x[i]+1);
}
else if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1];
a.push_back(x[i]-1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
for(int i=1;i<=n;i++){
if(pos[x[i]+2].count(y[i])){
u.push_back(i-1);
v.push_back(pos[x[i]+2][y[i]]);
a.push_back(x[i]+1);
if(!used[x[i]+1][y[i]-1]){
used[x[i]+1][y[i]-1]=1;
b.push_back(y[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1]=1;
b.push_back(y[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
if(pos[x[i]].count(y[i]+2)){
u.push_back(i-1);
v.push_back(pos[x[i]][y[i]+2]);
b.push_back(y[i]+1);
if(!used[x[i]-1][y[i]+1]){
used[x[i]-1][y[i]+1]=1;
a.push_back(x[i]-1);
}
else if(!used[x[i]+1][y[i]+1]){
used[x[i]+1][y[i]+1];
a.push_back(x[i]+1);
}
else{
u.clear();
v.clear();
a.clear();
b.clear();
break;
}
}
}
for(int i=0;i<=mx;i++)used[i].clear();
if(u.size()>0){
build(u,v,a,b);
return 1;
}
return 0;
}
int main() {
assert(scanf("%d", &n) == 1);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
build_called = false;
const int possible = construct_roads(x, y);
check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
if (possible == 1) {
check(build_called, "construct_roads() returned 1 without calling build()");
} else {
check(!build_called, "construct_roads() called build() but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
printf("%d\n", m);
for (int j = 0; j < m; j++) {
printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
}
}
fclose(stdout);
return 0;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:215:7: warning: variable 'xx' set but not used [-Wunused-but-set-variable]
215 | int xx=i;
| ^~
parks.cpp:161:7: warning: unused variable 'ok' [-Wunused-variable]
161 | bool ok=0;
| ^~
/usr/bin/ld: /tmp/ccUdWDGY.o: in function `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x270): multiple definition of `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/cc2L7FJ0.o:parks.cpp:(.text+0x980): first defined here
/usr/bin/ld: /tmp/ccUdWDGY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2L7FJ0.o:parks.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
