답안 #208803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208803 2020-03-12T08:01:20 Z E869120 경계 (BOI14_demarcation) C++14
0 / 100
37 ms 28944 KB
#include <iostream>
#include <vector>
#include <set>
#include <limits>
#include <cmath>
#include <tuple>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

// -------------------------------------- セグメントツリー ----------------------------------
class BIT {
public:
	int size_ = 1;
	vector<int> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		pos++; int s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

// ------------------------------------- ハッシュ関連の関数 ---------------------------------
long long BASE = 11111111111111LL;
long long power[1 << 18];
long long hush[1 << 18];

void init() {
	power[0] = 1;
	for (int i = 1; i <= 250000; i++) power[i] = BASE * power[i - 1];
}

// -------------------------------------- 幾何関連の関数 ------------------------------------
struct Point {
	long long px, py;
};

long long dst(Point a1, Point a2) {
	return abs(a1.px - a2.px) + abs(a1.py - a2.py);
}

vector<Point> fixes(vector<Point> G) {
	vector<Point> G2;
	for (int i = 0; i < G.size(); i++) {
		int pre = (i + G.size() - 1) % G.size(), nex = (i + 1) % G.size();
		bool s1 = false; if (G[pre].px == G[i].px) s1 = true;
		bool s2 = false; if (G[i].px == G[nex].px) s2 = true;
		if (s1 != s2) G2.push_back(G[i]);
	}
	return G2;
}

long long getmin(vector<long long> t) {
	hush[0] = 1;
	for (int i = 1; i <= t.size() * 2; i++) hush[i] = BASE * hush[i - 1] + t[(i - 1) % t.size()];

	long long minv = 9223372036854775807LL;
	for (int i = 0; i < t.size(); i++) {
		long long val = hush[t.size() + i] - hush[i] * power[t.size()];
		minv = min(minv, val);
	}
	return minv;
}

long long hashval(vector<Point> v) {
	vector<long long> t;
	for (int i = 0; i < v.size(); i++) {
		t.push_back(dst(v[i], v[(i + 1) % v.size()]));
	}
	long long p1 = getmin(t); reverse(t.begin(), t.end());
	long long p2 = getmin(t);
	return min(p1, p2);
}

bool identical(vector<Point> v1, vector<Point> v2) {
	v1 = fixes(v1);
	v2 = fixes(v2);
	if (v1.size() != v2.size()) return false;
	long long val1 = hashval(v1);
	long long val2 = hashval(v2);
	if (val1 == val2) return true;
	return false;
}

// ---------------------------------- 本質 ------------------------------------
long long N, L[1 << 18];
Point Z[1 << 18];

bool dir[1 << 18];
vector<pair<long long, int>> V[1 << 18][2];

vector<tuple<long long, int, int>> T[1 << 18][2];
set<tuple<long long, int, int>> Set;

// ---------------------------- その他のライブラリ ---------------------------
bool Rotate(int p1, int p2) {
	if (p1 > p2) p2 += N;
	if (p2 - p1 == 1) return true;
	return false;
}

long long getlen(int p1, int p2) {
	// p1 -> p2 の距離
	if (p1 > p2) p2 += N;
	return L[p2] - L[p1];
}

void adds(vector<Point>& a1, int cl, int cr) {
	if (cl > cr) cr += N;
	for (int i = cl; i <= cr; i++) {
		if (a1[a1.size() - 1].px == Z[i % N].px && a1[a1.size() - 1].py == Z[i % N].py) continue;
		a1.push_back(Z[i % N]);
	}
}

vector<Point> solve() {
	// ステップ A. 座標圧縮をする
	vector<long long> X, Y;
	for (int i = 0; i < N; i++) X.push_back(Z[i].px);
	for (int i = 0; i < N; i++) Y.push_back(Z[i].py);
	sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());

	// ステップ B. 初期化をする
	for (int i = 0; i <= N; i++) {
		V[i][0].clear();
		V[i][1].clear();
	}
	for (int i = 0; i <= N * 2; i++) {
		T[i][0].clear();
		T[i][1].clear();
	}

	// ステップ C. BIT で向きを求める(false: 左側、true: 右側)
	for (int i = 0; i < N; i++) {
		if (Z[i].px == Z[(i + 1) % N].px) continue;
		int pos1 = lower_bound(X.begin(), X.end(), Z[(i + 0) % N].px) - X.begin();
		int pos2 = lower_bound(X.begin(), X.end(), Z[(i + 1) % N].px) - X.begin();
		if (pos1 > pos2) swap(pos1, pos2);
		V[pos1][0].push_back(make_pair(Z[(i + 0) % N].py, i));
		V[pos2][1].push_back(make_pair(Z[(i + 0) % N].py, i));
	}
	BIT ZZ; ZZ.init(Y.size() + 2);
	for (int i = 0; i < X.size(); i++) {
		sort(V[i][0].begin(), V[i][0].end());
		for (pair<long long, int> j : V[i][1]) {
			int pos1 = lower_bound(Y.begin(), Y.end(), j.first) - Y.begin();
			ZZ.add(pos1, -1);
		}
		for (pair<long long, int> j : V[i][0]) {
			int pos1 = lower_bound(Y.begin(), Y.end(), j.first) - Y.begin();
			ZZ.add(pos1, 1);
			if (ZZ.sum(pos1) % 2 == 0) dir[j.second] = true;
			else dir[j.second] = false;
		}
	}

	// ステップ D. 境界値も含め、どこで push するか vector (T) に突っ込む
	for (int i = 0; i < N; i++) {
		if (Z[i].px == Z[(i + 1) % N].px) continue;
		int pos1 = lower_bound(X.begin(), X.end(), Z[(i + 0) % N].px) - X.begin();
		int pos2 = lower_bound(X.begin(), X.end(), Z[(i + 1) % N].px) - X.begin();
		int s0 = (i + N - 1) % N, s1 = (i + 0) % N, s2 = (i + 1) % N, s3 = (i + 2) % N;
		if (pos1 > pos2) { swap(pos1, pos2); swap(s1, s2); swap(s0, s3); }

		if (dir[i] == false) {
			int cl = pos1 * 2, cr = pos2 * 2;
			if (Z[s0].py > Z[s1].py) cl++;
			if (Z[s2].py > Z[s3].py) cr++;
			T[cl][0].push_back(make_tuple(Z[i].py, s1, s2));
			T[cr][1].push_back(make_tuple(Z[i].py, s1, s2));
		}
		else {
			int cl = pos1 * 2, cr = pos2 * 2;
			if (Z[s0].py < Z[s1].py) cl++;
			if (Z[s2].py < Z[s3].py) cr++;
			T[cl][0].push_back(make_tuple(Z[i].py, s1, s2));
			T[cr][1].push_back(make_tuple(Z[i].py, s1, s2));
		}
	}

	// ステップ E. 平面走査をする
	for (int i = 0; i <= (X.size() - 1) * 2; i++) {
		vector<tuple<long long, int, int>> Important;
		for (tuple<long long, int, int> j : T[i][1]) {
			auto itr = Set.lower_bound(j);
			if (itr != Set.begin()) { itr--; Important.push_back(*itr); itr++; }
			itr++; if (itr != Set.end()) { Important.push_back(*itr); }
			Set.erase(j);
		}
		for (tuple<long long, int, int> j : T[i][0]) {
			Important.push_back(j);
			Set.insert(j);
			auto itr = Set.lower_bound(j);
			if (itr != Set.begin()) { itr--; Important.push_back(*itr); itr++; }
			itr++; if (itr != Set.end()) { Important.push_back(*itr); }
		}

		long long vl, vr;
		if (i % 2 == 0) { vl = X[i / 2]; vr = X[i / 2]; }
		if (i % 2 == 1) { vl = X[i / 2] + 1; vr = X[(i + 1) / 2] - 1; }

		for(tuple<long long, int, int> j : Important) {
			auto itr = Set.lower_bound(j);
			if (itr == Set.end() || (*itr) != j) continue;
			int num = get<1>(j); if (Rotate(get<1>(j), get<2>(j)) == false) num = get<2>(j);
			if (dir[num] == true) itr--;

			tuple<long long, int, int> fl = (*itr); itr++;
			tuple<long long, int, int> fr = (*itr); itr++;
			long long L1 = 0;
			if (Rotate(get<1>(fl), get<2>(fl)) == true) L1 = getlen(get<1>(fr), get<1>(fl));
			if (Rotate(get<1>(fl), get<2>(fl)) == false) L1 = getlen(get<1>(fl), get<1>(fr));
			long long sl = L1 + abs(Z[get<1>(fl)].px - vl) + abs(Z[get<1>(fr)].px - vl);
			long long sr = L1 + abs(Z[get<1>(fl)].px - vr) + abs(Z[get<1>(fr)].px - vr);
			if (sl <= L[N] / 2LL && L[N] / 2LL <= sr && ((L[N] / 2LL) - sl) % 2LL == 0LL) {
				long long zahyou = vl + ((L[N] / 2LL) - sl) / 2LL;
				vector<Point> D1, D2;
				if (Rotate(get<1>(fl), get<2>(fl)) == true) {
					long long yl_val = get<0>(fl);
					long long yr_val = get<0>(fr);
					D1.push_back(Point{ zahyou, yr_val });
					adds(D1, get<1>(fr), get<1>(fl));
					if (D1[D1.size() - 1].px != zahyou || D1[D1.size() - 1].py != yl_val) D1.push_back({ zahyou, yl_val });
					D2.push_back(Point{ zahyou, yl_val });
					adds(D2, get<2>(fl), get<2>(fr));
					if (D2[D2.size() - 1].px != zahyou || D2[D2.size() - 1].py != yr_val) D2.push_back({ zahyou, yr_val });
				}
				if (Rotate(get<1>(fl), get<2>(fl)) == false) {
					long long yl_val = get<0>(fl);
					long long yr_val = get<0>(fr);
					D1.push_back(Point{ zahyou, yl_val });
					adds(D1, get<1>(fl), get<1>(fr));
					if (D1[D1.size() - 1].px != zahyou || D1[D1.size() - 1].py != yr_val) D1.push_back({ zahyou, yr_val });
					D2.push_back(Point{ zahyou, yr_val });
					adds(D2, get<2>(fr), get<2>(fl));
					if (D2[D2.size() - 1].px != zahyou || D2[D2.size() - 1].py != yl_val) D2.push_back({ zahyou, yl_val });
				}
				bool flag = identical(D1, D2);
				if (flag == true) {
					return vector<Point>{Point{ zahyou, get<0>(fl) }, Point{ zahyou, get<0>(fr) }};
				}
			}
		}
	}

	return vector<Point>{};
}

int main() {
	// ステップ 1. 入力・前準備
	scanf("%lld", &N); init();
	for (int i = 0; i < N; i++) scanf("%lld%lld", &Z[i].px, &Z[i].py);
	for (int i = 0; i < N * 2; i++) L[i + 1] = dst(Z[i % N], Z[(i + 1) % N]);
	for (int i = 1; i <= N * 2; i++) L[i] += L[i - 1];

	// ステップ 2. x 側を探索
	vector<Point> E1 = solve();
	if (E1.size() >= 1) {
		cout << E1[0].px << " " << E1[0].py << " " << E1[1].px << " " << E1[1].py << endl;
		return 0;
	}

	// ステップ 3. y 側を探索
	for (int i = 0; i < N; i++) swap(Z[i].px, Z[i].py);
	vector<Point> E2 = solve();
	if (E2.size() >= 1) {
		cout << E2[0].py << " " << E2[0].px << " " << E2[1].py << " " << E2[1].px << endl;
		return 0;
	}

	cout << "NO" << endl;
	return 0;
}

Compilation message

demarcation.cpp:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
demarcation.cpp: In function 'std::vector<Point> fixes(std::vector<Point>)':
demarcation.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'long long int getmin(std::vector<long long int>)':
demarcation.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= t.size() * 2; i++) hush[i] = BASE * hush[i - 1] + t[(i - 1) % t.size()];
                  ~~^~~~~~~~~~~~~~~
demarcation.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'long long int hashval(std::vector<Point>)':
demarcation.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp: In function 'std::vector<Point> solve()':
demarcation.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++) {
                  ~~^~~~~~~~~~
demarcation.cpp:198:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= (X.size() - 1) * 2; i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'int main()':
demarcation.cpp:267:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N); init();
  ~~~~~^~~~~~~~~~~~
demarcation.cpp:268:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%lld%lld", &Z[i].px, &Z[i].py);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp: In function 'std::vector<Point> solve()':
demarcation.cpp:230:56: warning: 'vr' may be used uninitialized in this function [-Wmaybe-uninitialized]
    long long sr = L1 + abs(Z[get<1>(fl)].px - vr) + abs(Z[get<1>(fr)].px - vr);
                                                     ~~~^~~~~~~~~~~~~~~~~~~~~~~
demarcation.cpp:229:56: warning: 'vl' may be used uninitialized in this function [-Wmaybe-uninitialized]
    long long sl = L1 + abs(Z[get<1>(fl)].px - vl) + abs(Z[get<1>(fr)].px - vl);
                                                     ~~~^~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 28940 KB Output is correct
2 Correct 23 ms 27128 KB Output is correct
3 Correct 22 ms 27000 KB Output is correct
4 Correct 37 ms 28756 KB Output is correct
5 Correct 21 ms 26872 KB Output is correct
6 Correct 21 ms 26872 KB Output is correct
7 Incorrect 21 ms 26872 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 27000 KB Output is correct
2 Correct 22 ms 27000 KB Output is correct
3 Correct 21 ms 26872 KB Output is correct
4 Correct 21 ms 27000 KB Output is correct
5 Incorrect 21 ms 27000 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 26876 KB Output is correct
2 Correct 21 ms 26872 KB Output is correct
3 Correct 22 ms 26876 KB Output is correct
4 Correct 21 ms 26872 KB Output is correct
5 Incorrect 21 ms 27000 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 28944 KB Output is correct
2 Correct 21 ms 27000 KB Output is correct
3 Correct 22 ms 26872 KB Output is correct
4 Correct 35 ms 28756 KB Output is correct
5 Correct 21 ms 26872 KB Output is correct
6 Correct 22 ms 26872 KB Output is correct
7 Incorrect 21 ms 26872 KB Output isn't correct
8 Halted 0 ms 0 KB -