結果

問題 No.2177 Recurring ab
コンテスト
ユーザー MasKoaTS
提出日時 2022-09-18 14:59:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 9,607 bytes
コンパイル時間 9,423 ms
コンパイル使用メモリ 277,856 KB
最終ジャッジ日時 2025-02-07 11:42:47
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 2 MLE * 1
other TLE * 9 MLE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
In constructor ‘Point::Point(int, int)’,
    inlined from ‘Point* getRectangle(V<Point>&)’ at main.cpp:128:29:
main.cpp:73:25: warning: ‘x’ may be used uninitialized [-Wmaybe-uninitialized]
   73 |                 this->x = x;
      |                 ~~~~~~~~^~~
main.cpp: In function ‘Point* getRectangle(V<Point>&)’:
main.cpp:117:13: note: ‘x’ was declared here
  117 |         int x, y;
      |             ^
In constructor ‘Point::Point(int, int)’,
    inlined from ‘Point* getRectangle(V<Point>&)’ at main.cpp:128:29:
main.cpp:74:25: warning: ‘y’ may be used uninitialized [-Wmaybe-uninitialized]
   74 |                 this->y = y;
      |                 ~~~~~~~~^~~
main.cpp: In function ‘Point* getRectangle(V<Point>&)’:
main.cpp:117:16: note: ‘y’ was declared here
  117 |         int x, y;
      |                ^

ソースコード

diff # 

#include <math.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define print(n) cout << (n) << endl
#define fprint(n) cout << setprecision(16) << (n) << endl
#define ceil_div(a, b) (((a) - 1) / (b) + 1)
#define rep(i, l, n) for (int i = (l); i < (n); i++)
#define itrep(itr, st) for (auto itr = st.begin(); itr != st.end(); itr++)
#define ite(i, a) for (auto& i : a)
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define lbi(A, x) (ll)(lb(all(A), x) - A.begin())
#define ubi(A, x) (ll)(ub(all(A), x) - A.begin())
using str = string;
using ll = long long;
using Pair = pair<int, int>;
using mint = modint1000000007;
using Mint = modint998244353;
template <class T>	using V = vector<T>;
template <class T>	using VV = V<V<T> >;
template <class T>	using PQ = priority_queue<T, V<T>, greater<T> >;
template <class T>	using PQR = priority_queue<T>;
template <class T>	using BIT = fenwick_tree<T>;
const ll INF = 4611686018427387903;
const int inf = 2147483647;
const ll mod = 1000000007;
const ll MOD = 998244353;
template <class T>  inline V<T> getList(int n) { V<T> res(n); rep(i, 0, n) { cin >> res[i]; }return res; }
template <class T>  inline VV<T> getGrid(int m, int n) { VV<T> res(m, V<T>(n)); rep(i, 0, m) { res[i] = getList<T>(n); }return res; }
template <class T> inline void prints(V<T>& vec) { if (vec.size() == 0)return; cout << vec[0];	rep(i, 1, vec.size()) { cout << ' ' << vec[i]; } cout << '\n'; }
inline V<int> dtois(string& s) { V<int> vec = {}; ite(e, s) { vec.push_back(e - '0'); } return vec; }
inline V<int> atois(string& s) { V<int> vec = {}; ite(e, s) { vec.push_back(e - 'a'); } return vec; }
inline V<int> Atois(string& s) { V<int> vec = {}; ite(e, s) { vec.push_back(e - 'A'); } return vec; }

#define TIME 900


//グローバル変数
int N, M, C;
struct Point;
V<Point> points;
V<BIT<int> > xbt;
V<BIT<int> > ybt;
V<BIT<int> > nxbt;
V<BIT<int> > nybt;
V<BIT<int> > lxbt;
V<BIT<int> > lybt;
V<BIT<int> > lnxbt;
V<BIT<int> > lnybt;
V<V<Point> > ans = {};	//答えとなる点の集合


//２乗
inline int squ(int x) {
	return x * x;
}


//二次元平面上の点
struct Point {
	int x;
	int y;

	Point(void) {
		x = 0;
		y = 0;
	}

	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}

	int weight(void) const{
		return squ(this->x - C) + squ(this->y - C) + 1;
	}

	bool operator<(const Point other) const {
		int a = this->weight();
		int b = other.weight();
		if (a == b) {
			return tie(this->x, this->y) < tie(other.x, other.y);
		}
		return a > b;
	}
};


//時間計測系
using chrono::duration_cast;
using chrono::milliseconds;
using chrono::system_clock;
inline int getnow() { return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count(); }

//乱数系
mt19937 mt{ random_device{}() };
uniform_int_distribution<> rand03(0, 3);


//3点から長方形の最後の1点を得る
Point* getRectangle(V<Point>& point_vec) {
	assert(point_vec.size() == 3);
	set<int> xst = {};
	set<int> yst = {};
	set<Point> pst = {};
	for (Point p : point_vec) {
		pst.insert(p);
		xst.insert(p.x);
		yst.insert(p.y);
	}
	if (xst.size() != 2 or yst.size() != 2) {
		return NULL;
	}
	int x, y;
	itrep(itr_x, xst) {
		itrep(itr_y, yst) {
			Point p = Point(*itr_x, *itr_y);
			if (pst.find(p) != pst.end()) {
				continue;
			}
			x = p.x;
			y = p.y;
		}
	}
	Point* ret = new Point(x, y);
	return ret;
}


//4点を長方形をなすように並び替えた配列を得る
V<Point> getSortedRectangle(V<Point>& point_vec) {
	assert(point_vec.size() == 4);
	V<Point> ret = { point_vec[0] };
	set<Point> pst = { point_vec[0] };
	rep(i, 0, 3) {
		for (Point p : point_vec) {
			if (p.x != ret[i].x and p.y != ret[i].y) {
				continue;
			}
			if (pst.find(p) != pst.end()) {
				continue;
			}
			ret.push_back(p);
			pst.insert(p);
			break;
		}
	}
	/*if (ret.size() != 4) {
		cout << "point_vec" << endl;
		for (Point p : point_vec) {
			cout << p.x << ' ' << p.y << endl;
		}
		cout << "pst" << endl;
		itrep(itr, pst) {
			Point p = *itr;
			cout << p.x << ' ' << p.y << endl;
		}
		cout << "ret" << endl;
		for (Point p : ret) {
			cout << p.x << ' ' << p.y << endl;
		}
		assert(false);
	}*/
	return ret;
}


//長方形の最後の1点を調べて追加（まっすぐ）
void addStraightRectangle(int i, int j, int k) {
	V<Point> point_vec = { points[i],points[j],points[k] };
	Point* p = getRectangle(point_vec);
	if (p == NULL or xbt[p->y].sum(p->x, p->x + 1) != 0) {
		return;
	}
	V<Point> vec = { *p,points[i],points[j],points[k] };
	vec = getSortedRectangle(vec);

	//作る長方形が条件を満たしているかチェック
	vec.push_back(*p);
	bool flag = true;
	rep(l, 0, 4) {
		//x座標が同じ場合
		if (vec[l].x == vec[l + 1].x) {
			int x = vec[l].x;
			int y1 = min(vec[l].y, vec[l + 1].y);
			int y2 = max(vec[l].y, vec[l + 1].y);
			flag &= (ybt[x].sum(y1 + 1, y2) == 0) & (lybt[x].sum(y1, y2) == 0);
		}
		//y座標が同じ場合
		if (vec[l].y == vec[l + 1].y) {
			int y = vec[l].y;
			int x1 = min(vec[l].x, vec[l + 1].x);
			int x2 = max(vec[l].x, vec[l + 1].x);
			flag &= (xbt[y].sum(x1 + 1, x2) == 0) & (lxbt[y].sum(x1, x2) == 0);
		}
		if (flag == false) {
			break;
		}
	}
	if (flag == false) {
		return;
	}

	//長方形・点の追加
	rep(l, 0, 4) {
		//x座標が同じ場合
		if (vec[l].x == vec[l + 1].x) {
			int x = vec[l].x;
			int y1 = min(vec[l].y, vec[l + 1].y);
			int y2 = max(vec[l].y, vec[l + 1].y);
			rep(y, y1, y2) {
				lybt[x].add(y, 1);
			}
		}
		//y座標が同じ場合
		if (vec[l].y == vec[l + 1].y) {
			int y = vec[l].y;
			int x1 = min(vec[l].x, vec[l + 1].x);
			int x2 = max(vec[l].x, vec[l + 1].x);
			rep(x, x1, x2) {
				lxbt[y].add(x, 1);
			}
		}
	}
	vec.pop_back();
	ans.push_back(vec);
	points.push_back(*p);
	xbt[p->y].add(p->x, 1);
	ybt[p->x].add(p->y, 1);
	int nx = p->x + p->y, ny = p->x - p->y + (N - 1);
	nxbt[ny].add(nx, 1);
	nybt[nx].add(ny, 1);
	M++;
}


//長方形の最後の1点を調べて追加（斜め）
void addDiagonalRectangle(int i, int j, int k) {
	Point p1 = Point(points[i].x + points[i].y, points[i].x - points[i].y + (N - 1));
	Point p2 = Point(points[j].x + points[j].y, points[j].x - points[j].y + (N - 1));
	Point p3 = Point(points[k].x + points[k].y, points[k].x - points[k].y + (N - 1));
	V<Point> point_vec = { p1,p2,p3 };
	Point* p = getRectangle(point_vec);
	if (p == NULL or nxbt[p->y].sum(p->x, p->x + 1) != 0) {
		return;
	}
	V<Point> vec = { *p,p1,p2,p3 };
	vec = getSortedRectangle(vec);

	//作る長方形が条件を満たしているかチェック
	vec.push_back(*p);
	bool flag = true;
	rep(l, 0, 4) {
		//x座標が同じ場合
		if (vec[l].x == vec[l + 1].x) {
			int x = vec[l].x;
			int y1 = min(vec[l].y, vec[l + 1].y);
			int y2 = max(vec[l].y, vec[l + 1].y);
			flag &= (nybt[x].sum(y1 + 1, y2) == 0) & (lnybt[x].sum(y1, y2) == 0);
		}
		//y座標が同じ場合
		if (vec[l].y == vec[l + 1].y) {
			int y = vec[l].y;
			int x1 = min(vec[l].x, vec[l + 1].x);
			int x2 = max(vec[l].x, vec[l + 1].x);
			flag &= (nxbt[y].sum(x1 + 1, x2) == 0) & (lnxbt[y].sum(x1, x2) == 0);
		}
		if (flag == false) {
			break;
		}
	}
	if (flag == false) {
		return;
	}

	//長方形・点の追加
	rep(l, 0, 4) {
		//x座標が同じ場合
		if (vec[l].x == vec[l + 1].x) {
			int x = vec[l].x;
			int y1 = min(vec[l].y, vec[l + 1].y);
			int y2 = max(vec[l].y, vec[l + 1].y);
			rep(y, y1, y2) {
				lnybt[x].add(y, 1);
			}
		}
		//y座標が同じ場合
		if (vec[l].y == vec[l + 1].y) {
			int y = vec[l].y;
			int x1 = min(vec[l].x, vec[l + 1].x);
			int x2 = max(vec[l].x, vec[l + 1].x);
			rep(x, x1, x2) {
				lnxbt[y].add(x, 1);
			}
		}
	}
	vec.pop_back();
	nxbt[p->y].add(p->x, 1);
	nybt[p->x].add(p->y, 1);
	//まっすぐの点に直す
	V<Point> nvec = {};
	for (Point np : vec) {
		int x = (np.x + np.y - (N - 1)) >> 1;
		int y = (np.x - np.y + (N - 1)) >> 1;
		nvec.push_back({ x,y });
	}
	ans.push_back(nvec);
	int x = (p->x + p->y - (N - 1)) >> 1;
	int y = (p->x - p->y + (N - 1)) >> 1;
	points.push_back({ x,y });
	xbt[y].add(x, 1);
	ybt[x].add(y, 1);
	M++;
}




//メイン
int main(void) {
	//時間計測開始
	int time_limit = getnow() + TIME;

	//入力
	cin >> N >> M;
	C = (N - 1) >> 1;
	points = V<Point>(M);
	xbt = V<BIT<int> >(N, BIT<int>(N));
	ybt = V<BIT<int> >(N, BIT<int>(N));
	nxbt = V<BIT<int> >(N << 1, BIT<int>(N << 1));
	nybt = V<BIT<int> >(N << 1, BIT<int>(N << 1));
	rep(i, 0, M) {
		int x, y;	cin >> x >> y;
		xbt[y].add(x, 1);
		ybt[x].add(y, 1);
		points[i] = Point(x, y);
		int nx = x + y, ny = x - y + (N - 1);
		nxbt[ny].add(nx, 1);
		nybt[nx].add(ny, 1);
	}
	//sort(all(points));
	
	//既に追加した線分の集合
	lxbt = V<BIT<int> >(N, BIT<int>(N - 1));
	lybt = V<BIT<int> >(N, BIT<int>(N - 1));
	lnxbt = V<BIT<int> >(N << 1, BIT<int>((N << 1) - 1));
	lnybt = V<BIT<int> >(N << 1, BIT<int>((N << 1) - 1));

	//時間の許す限り探索
	while (true) {
		//3点の組み合わせを調べる
		rep(i, 0, M - 2) {
			rep(j, i + 1, M - 1) {
				rep(k, j + 1, M) {
					//時間の許す限り探索
					if (getnow() >= time_limit) {
						goto OUTPUT;
					}

					//長方形の最後の1点を調べて追加（まっすぐ）
					addStraightRectangle(i, j, k);
					
					//長方形の最後の1点を調べて追加（斜め）
					addDiagonalRectangle(i, j, k);
				}
			}
		}
	}

OUTPUT:
	//答えを出力
	cout << ans.size() << endl;
	for (V<Point> vec : ans) {
		cout << vec[0].x << ' ' << vec[0].y;
		rep(i, 1, 4) {
			cout << ' ' << vec[i].x << ' ' << vec[i].y;
		}
		cout << '\n';
	}

	return 0;
}
0