#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);
}
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:265:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &N); init();
~~~~~^~~~~~~~~~~~
demarcation.cpp:266: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:228: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:227: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);
~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
28940 KB |
Output is correct |
| 2 |
Correct |
22 ms |
27000 KB |
Output is correct |
| 3 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 4 |
Correct |
35 ms |
28756 KB |
Output is correct |
| 5 |
Correct |
22 ms |
27000 KB |
Output is correct |
| 6 |
Correct |
21 ms |
27000 KB |
Output is correct |
| 7 |
Incorrect |
21 ms |
26872 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
26872 KB |
Output is correct |
| 2 |
Correct |
22 ms |
26872 KB |
Output is correct |
| 3 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 4 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 5 |
Incorrect |
21 ms |
26976 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
26872 KB |
Output is correct |
| 2 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 3 |
Correct |
22 ms |
26872 KB |
Output is correct |
| 4 |
Correct |
22 ms |
26872 KB |
Output is correct |
| 5 |
Incorrect |
21 ms |
27000 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
28940 KB |
Output is correct |
| 2 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 3 |
Correct |
21 ms |
26872 KB |
Output is correct |
| 4 |
Correct |
36 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 |
22 ms |
26872 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
