Submission #12869

#TimeUsernameProblemLanguageResultExecution timeMemory
12869aintaDemarcation (BOI14_demarcation)C++98
100 / 100
126 ms19140 KiB
#include<stdio.h> #include<algorithm> #include<vector> #include<set> #define INF 1111111111 using namespace std; #define SIT set<A>::iterator int n, cnt, chk, m; vector<int>E[101000]; struct Rect{ int x1, x2, y1, y2; long long S; }R[101000]; struct A{ int y1, y2, x; bool operator<(const A &p)const{ return y2 != p.y2 ? y2 < p.y2 : y1 < p.y1; } }; struct Seg{ int x, y1, y2; bool operator<(const Seg &p)const{ return x < p.x; } }w[101000]; struct point{ int x, y; }P[101000], P1[101000], P2[101000]; void Make_Seg(){ int i; m = 0; for (i = 0; i < n; i++){ if (P[i].x == P[i + 1].x){ w[m].x = P[i].x; w[m].y1 = min(P[i].y, P[i + 1].y); w[m].y2 = max(P[i].y, P[i + 1].y); m++; } } sort(w, w + m); } set<A> Set; void Make(int x1, int x2, int y1, int y2){ if (x1 == x2)return; cnt++; R[cnt].x1 = x1, R[cnt].x2 = x2, R[cnt].y1 = y1, R[cnt].y2 = y2; R[cnt].S = (long long)(y2 - y1)*(x2 - x1); } void Ins(int x, int y1, int y2){ A tp; tp.x = x, tp.y1 = y1, tp.y2 = y2; Set.insert(tp); } void Del(SIT it, Seg s){ int x = it->x, y1 = it->y1, y2 = it->y2; Set.erase(it); Make(x, s.x, y1, y2); if (s.y1 != y1){ Ins(s.x, y1, s.y1); } if (s.y2 != y2){ Ins(s.x, s.y2, y2); } } void Make_Rect(){ int i, y1, y2, ck; A tp; SIT it, it2; cnt = 0; for (i = 0; i < m; i++){ tp.x = 0, tp.y1 = -1, tp.y2 = w[i].y2; it = Set.lower_bound(tp); if (it != Set.end() && it->y1 <= w[i].y1){ Del(it, w[i]); continue; } y1 = w[i].y1, y2 = w[i].y2; ck = 0; if (it != Set.end() && it->y1 == w[i].y2){ y2 = it->y2; Make(it->x, w[i].x, it->y1, it->y2); ck += 1; } if (it != Set.begin()){ it2 = it; it2--; if (it2->y2 == w[i].y1){ y1 = it2->y1; Make(it2->x, w[i].x, it2->y1, it2->y2); ck += 2; } } if (ck & 1)Set.erase(it); if (ck & 2)Set.erase(it2); Ins(w[i].x, y1, y2); } Set.clear(); } void Make_Tree(){ int i, ck; A tp; SIT it, it2, it3; for (i = 1; i <= cnt; i++){ tp.x = 0, tp.y2 = R[i].y2, tp.y1 = -1; it = Set.lower_bound(tp); ck = 0; if (it != Set.begin()){ it2 = it; it2--; while (1){ if (it2->y2 <= R[i].y1)break; if (R[it2->x].x2 == R[i].x1){ E[it2->x].push_back(i); E[i].push_back(it2->x); } if (it2 != Set.begin()){ it3 = it2; it3--; } else ck = 1; if (it2->y1 < R[i].y1){ Ins(it2->x, it2->y1, R[i].y1); } Set.erase(it2); if (!ck)it2 = it3; else break; } } if(it != Set.end() && it->y1 < R[i].y2){ if (R[it->x].x2 == R[i].x1){ E[it->x].push_back(i); E[i].push_back(it->x); } if (it->y1 < R[i].y1){ Ins(it->x, it->y1, R[i].y1); } if (it->y2 > R[i].y2){ Ins(it->x, R[i].y2, it->y2); } Set.erase(it); } Ins(i, R[i].y1, R[i].y2); } Set.clear(); } long long D[101000]; bool On(point a, point b, int x, int y){ if (a.x == x && b.x == x){ if (min(b.y, a.y) <= y && y <= max(b.y, a.y))return true; } else if (a.y == y && b.y == y){ if (min(b.x, a.x) <= x && x <= max(b.x, a.x))return true; } return false; } bool On2(int a, int x, int y){ a %= n; int b = (a + n - 1) % n; return On(P[a], P[b], x, y); } int c1, c2; bool Deleted[101000]; void Cut_Poly(int x, int y1, int y2){ int i, t, pv1, pv2, cc = 0; c1 = 0; for (i = 0; i <= n; i++){ if (P[i].x == x && P[i].y == y1)break; if (i && On2(i, x, y1))break; } if (x != P[i].x || y1 != P[i].y){ P1[c1].x = x, P1[c1].y = y1; c1++; } t = i%n; while (1){ P1[c1].x = P[t].x, P1[c1].y = P[t].y; c1++; t = (t + 1) % n; if (On2(t, x, y2))break; } P1[c1].x = x, P1[c1].y = y2; c1++; for (i = 0; i < c1; i++){ pv1 = (i + c1 - 1) % c1; pv2 = (i + 1) % c1; Deleted[i] = false; if (On(P1[pv1], P1[pv2], P1[i].x, P1[i].y))Deleted[i] = true; } for (i = 0; i < c1; i++){ if (!Deleted[i])P1[cc++] = P1[i]; } c1 = cc; } void Rotate(){ int i, t; for (i = 0; i < c1; i++){ t = P1[i].x; P1[i].x = P1[i].y; P1[i].y = -t; } } bool Match(){ int i, x, y, j, Mx = INF, My = INF, t1, t2; for (i = 0; i < c1; i++){ if (Mx > P1[i].x || (Mx == P1[i].x && My > P1[i].y)){ Mx = P1[i].x, My = P1[i].y, t1 = i; } } Mx = My = INF; for (i = 0; i < c1; i++){ if (Mx > P2[i].x || (Mx == P2[i].x && My > P2[i].y)){ Mx = P2[i].x, My = P2[i].y, t2 = i; } } Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y; for (i = 0; i < c1; i++){ if (P1[(t1 + i) % c1].x - P2[(t2 + i) % c1].x != Mx)break; if (P1[(t1 + i) % c1].y - P2[(t2 + i) % c1].y != My)break; } if (i == c1)return true; for (i = 0; i < c1; i++){ if (P1[(t1 + i) % c1].x - P2[(t2 + c1 - i) % c1].x != Mx)break; if (P1[(t1 + i) % c1].y - P2[(t2 + c1 - i) % c1].y != My)break; } return i == c1; } bool Same(){ int i; if (c1 != c2)return false; if (Match())return true; for (i = 0; i < 3; i++){ Rotate(); if (Match())return true; } for (i = 0; i < c1; i++)P1[i].x = -P1[i].x; if (Match())return true; for (i = 0; i < 3; i++){ Rotate(); if (Match())return true; } return false; } bool Check(int x, int y1, int y2){ int i; Cut_Poly(x, y1, y2); for (i = 0; i < c1; i++)P2[i] = P1[i]; c2 = c1; Cut_Poly(x, y2, y1); if (!Same())return false; if (!chk)printf("%d %d %d %d", x, y1, x, y2); else printf("%d %d %d %d", y1, x, y2, x); return true; } void DFS(int a, int pp){ int i, x; D[a] = R[a].S; for (i = 0; i < E[a].size(); i++){ x = E[a][i]; if (x == pp)continue; DFS(E[a][i], a); D[a] += D[E[a][i]]; } } bool DP(int a, int pp){ int i, x; long long t, S1 = 0, S2 = 0, M, y; if (pp){ M = D[pp]; D[pp] -= D[a]; D[a] = M; } else M = D[a]; for (i = 0; i < E[a].size(); i++){ x = E[a][i]; if (R[x].x1 < R[a].x1){ if (D[x] * 2 == M){ if (Check(R[x].x2, max(R[x].y1, R[a].y1), min(R[x].y2, R[a].y2)))return true; } S1 += D[x]; } else{ if (D[x] * 2 == M){ if (Check(R[x].x1, max(R[x].y1, R[a].y1), min(R[x].y2, R[a].y2)))return true; } S2 += D[x]; } } t = S2 - S1 + R[a].S; y = R[a].y2 - R[a].y1; if (t >= 0 && t % (2 * y) == 0){ t = t / (2 * y); if (t <= R[a].x2 - R[a].x1){ if (Check(R[a].x1 + t, R[a].y1, R[a].y2))return true; } } for (i = 0; i < E[a].size(); i++){ if (E[a][i] != pp){ if (DP(E[a][i], a))return true; } } D[a] = D[a] - D[pp]; D[pp] = M; return false; } bool Dynamic(){ int i; DFS(1, 0); return DP(1, 0); } void init(){ int i; for (i = 1; i <= cnt; i++){ E[i].clear(); } } bool Pos(){ Make_Seg(); Make_Rect(); Make_Tree(); if (Dynamic())return true; init(); return false; } int main(){ //freopen("input.txt", "r", stdin); int i; scanf("%d", &n); for (i = 0; i < n; i++){ scanf("%d%d", &P[i].x, &P[i].y); } P[n] = P[0]; if (Pos()){ return 0; } for (i = 0; i <= n; i++)swap(P[i].x, P[i].y); chk = 1; if (Pos()){ return 0; } printf("NO\n"); }

Compilation message (stderr)

demarcation.cpp: In function 'bool Match()':
demarcation.cpp:207:9: warning: unused variable 'x' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
         ^
demarcation.cpp:207:12: warning: unused variable 'y' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
            ^
demarcation.cpp:207:15: warning: unused variable 'j' [-Wunused-variable]
  int i, x, y, j, Mx = INF, My = INF, t1, t2;
               ^
demarcation.cpp: In function 'void DFS(int, int)':
demarcation.cpp:261:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp: In function 'bool DP(int, int)':
demarcation.cpp:279:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp:302:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
                ^
demarcation.cpp: In function 'bool Dynamic()':
demarcation.cpp:313:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:337:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
demarcation.cpp:339:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &P[i].x, &P[i].y);
                                  ^
demarcation.cpp: In function 'bool Match()':
demarcation.cpp:219:25: warning: 't2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y;
                         ^
demarcation.cpp:219:14: warning: 't1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Mx = P1[t1].x - P2[t2].x, My = P1[t1].y - P2[t2].y;
              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...