| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 18450 | youngyojun | Demarcation (BOI14_demarcation) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define pb push_back
#define sz(V) ((int)(V).size())
#define srtv(V) sort((V).begin(),(V).end())
#define bbef(V) ((V)[((sz((V)))-2)])
#define nxtv(V, index) ((V)[(((index)+1)%(sz(V)))])
using namespace std;
typedef long long ll;
typedef pair<int, int> pairii;
// 정점 정보 구조체
struct Point {
int x, y; // X좌표, Y좌표
Point() {}
Point(const int _x, const int _y) : x(_x), y(_y) {}
bool operator == (const Point& t) const { return ((x == t.x) && (y == t.y)); }
};
// 답의 후보(세로선) 정보 구조체
struct HuboLine {
int x0, x1, y; // X시작 좌표, X끝 좌표, Y좌표 (x0 < x1)
HuboLine() {}
HuboLine(const int _x0, const int _x1, const int _y) : x0(_x0), x1(_x1), y(_y) {}
};
// Sweep Line 가로선 정점 정보 구조체
struct SweepInfo {
int x, y, idx; // X좌표, Y좌표, 시작 정점의 index
bool dir, isend; // 방향성, 이후 소멸 여부 : false=>오른쪽, true=>왼쪽
SweepInfo() {}
SweepInfo(const int _x, const int _y, const int _idx, const bool _dir, const bool _isend) : x(_x), y(_y), idx(_idx), dir(_dir), isend(_isend) {}
bool operator < (const SweepInfo& t) const { return ((y != t.y) ? (y < t.y) : ((isend != t.isend) ? (isend) : (x < t.x))); }
};
vector<Point> Points;
vector<ll> DlenR;
vector<HuboLine> HuboLines;
// 입력 처리
// points : empty
void Input(vector<Point>& points) {
int N, x, y; scanf("%d", &N);
for(int i = 0; i < N; scanf("%d%d", &x, &y), points.pb(Point(x, y)), i++);
}
// 도형 반전 변환 처리
void Reflect(vector<Point>& points) { for(int i = 0; i < sz(points); swap(points[i].x, points[i].y), i++); }
// 도형 회전 변환 처리 (시계방향으로 90도, (0, 0) 중심)
void Rotate(vector<Point>& points) { for(int i = 0; i < sz(points); swap(points[i].x, points[i].y), points[i].y *= (-1), i++); }
// 두 도형 비교 처리 (회전, 반전 처리 안함) : poly1 = poly2 => true
// poly1, poly2 : Reindexed 필요
bool CompareSimple(const vector<Point>& poly1, const vector<Point>& poly2) {
if(sz(poly1) != sz(poly2)) return false;
int dx = (poly1[0].x - poly2[0].x), dy = (poly1[0].y - poly2[0].y);
for(int i = 1; i < sz(poly1); i++) {
if(((poly1[i].x - poly2[i].x) != dx) || ((poly1[i].y - poly2[i].y) != dy)) return false;
}
return true;
}
// 최좌상점의 index 반환 함수
int GetULIndex(const vector<Point>& points) {
int index = 0;
for(int i = 1; i < sz(points); i++) {
if((points[i].y < points[index].y) ||
((points[i].y == points[index].y) && (points[i].x < points[index].x))) index = i;
}
return index;
}
// 도형 최적화 처리 (P0, 방향 지정)
// points : 1 < size
void Reindexed(vector<Point>& points) {
vector<Point> tmppoints = points;
int ulindex = GetULIndex(points);
for(int i = 0; i < sz(points); points[(sz(points) - ulindex + i) % sz(points)] = tmppoints[i], i++);
if(points[0].x != points[1].x) {
for(int i = 1; i < (sz(points) / 2); swap(points[i], points[sz(points) - i]), i++);
}
}
// 두 도형 비교 처리 (회전, 반전 처리 포함) : poly1 = poly2 => true
bool Compare(vector<Point>& poly1, vector<Point>& poly2) {
if(sz(poly1) != sz(poly2)) return false;
Reindexed(poly2);
for(int i = 0; i < 2; i++) {
if(i) Reflect(poly1);
for(int j = 0; j < 4; j++) {
Rotate(poly1); Reindexed(poly1);
if(CompareSimple(poly1, poly2)) return true;
}
}
return false;
}
// long long 변수의 절대값 반환 함수
ll abs(const ll num) { return ((num < 0) ? (-num) : num); }
// 세 점 일직선 여부 반환 함수 (수직, 수평만 확인)
bool IsOnLine(const Point& p1, const Point& p2, const Point& p3) { return (((p1.x == p2.x) && (p2.x == p3.x)) || ((p1.y == p2.y) && (p2.y == p3.y))); }
// 두 점간의 거리 반환 함수 (수직, 수평만 정상 작동)
ll GetDistance(const Point& p1, const Point& p2) { return abs((ll)((p1.x - p2.x) + (p1.y - p2.y))); }
// 복합 도형 단순 최적화 처리 (일직선, 같은 위치의 점 제거)
void OptimizePolygon(vector<Point>& points) {
vector<Point> tmppoints = points; points.clear();
for(int i = 0; i < sz(tmppoints); i++) {
if((!points.empty()) && (points.back() == tmppoints[i])) continue;
if((1 < sz(points)) && IsOnLine(points.back(), bbef(points), tmppoints[i])) points.pop_back();
points.pb(tmppoints[i]);
}
}
// 도형 분할 처리 : points -> (poly1, poly2) by line
// poly1, poly2 : empty
// line : available
void SplitPolygonWithLine(const vector<Point>& points, vector<Point>& poly1, vector<Point>& poly2, const HuboLine line) {
for(int index = 0, cnt = 0; index < sz(points); cnt++) {
for(; index < sz(points); index++) {
if(cnt % 2) poly1.pb(points[index]);
else poly2.pb(points[index]);
if((points[index].x == nxtv(points, index).x)) { // 선분(points[index], points[index+1])이 가로선이면,
// (line.x0, line.y)가 선분 위에 있는 경우
if((points[index].x == line.x0) && (points[index].y <= line.y) && (line.y <= nxtv(points, index).y)) {
poly1.pb(Point(line.x0, line.y)); poly2.pb(Point(line.x0, line.y)); index++; break;
}
// (line.x1, line.y)가 선분 위에 있는 경우
if((points[index].x == line.x1) && (nxtv(points, index).y <= line.y) && (line.y <= points[index].y)) {
poly1.pb(Point(line.x1, line.y)); poly2.pb(Point(line.x1, line.y)); index++; break;
}
}
}
}
OptimizePolygon(poly1); OptimizePolygon(poly2);
}
// 도형 분할 및 비교 처리 : (points, line) = Answer => true
// line : available
bool CheckSplitLineIsAnswer(const vector<Point>& points, const HuboLine line) {
vector<Point> poly1, poly2; SplitPolygonWithLine(points, poly1, poly2, line);
return Compare(poly1, poly2);
}
// dlenR 표 생성 함수
// dlenR : empty
void MakeDP_dlenR(const vector<Point>& points, vector<ll>& dlenR) {
dlenR.pb(0LL); // dlenR[0] = 0
for(int i = 1; i <= sz(points); dlenR.pb(dlenR.back() + GetDistance(points[i - 1], points[i % sz(points)])), i++);
}
// HuboLine 값 생성 및 삽입 함수
void InsertHubo(const vector<Point>& points, const vector<ll>& dlenR, vector<HuboLine>& hubos, const int A, const int B) {
ll Sum = 0, t = 0;
if(A < B) Sum = (((ll)points[A + 1].y) + points[B - 1].y + dlenR[B - 1] - dlenR[A + 1] - (dlenR[sz(points)] / 2));
else Sum = (((ll)dlenR[B]) + points[A].y + points[B].y + (dlenR[sz(points)] / 2) - dlenR[A]);
if(Sum % 2) return;
t = Sum / 2;
if((ll)points[A].y <= t && t <= (ll)points[A + 1].y && (ll)points[B].y <= t && t <= (ll)points[B - 1].y)
hubos.pb(HuboLine(points[A].x, points[B].x, (int)t));
}
// HuboLine 생성 함수
// points : Reindexed 필요
void MakeHubo(const vector<Point>& points, const vector<ll>& dlenR, vector<HuboLine>& hubos) {
set<int> YCoops; set<int>::iterator Yit;
vector<SweepInfo> sweeps; int Swpit = 0;
set<pair<int, pair<int, bool> > > XSweep; // pair<X좌표, pair<시작 정점의 index, 방향성>>
// Sweep Line 정보 생성
for(int i = 0; i < sz(points); i += 2) {
// Right Direction
if(points[i].y < points[i + 1].y) {
sweeps.pb(SweepInfo(points[i].x, points[i].y, i, false, false));
sweeps.pb(SweepInfo(points[i + 1].x, points[i + 1].y + 1, i, false, true));
}
// Left Direction
else {
sweeps.pb(SweepInfo(points[i + 1].x, points[i + 1].y, i + 1, true, false));
sweeps.pb(SweepInfo(points[i].x, points[i].y + 1, i + 1, true, true));
}
}
srtv(sweeps);
for(int i = 0; i < sz(sweeps); YCoops.insert(sweeps[i].y), i++);
// Line Sweep Algorithm
for(Yit = YCoops.begin(); Yit != YCoops.end(); Yit++) {
// Delete Lines
for(; Swpit < sz(sweeps) && sweeps[Swpit].y == (*Yit) && sweeps[Swpit].isend; Swpit++) {
XSweep.erase(XSweep.find(pair<int, pair<int, bool> >(sweeps[Swpit].x, pair<int, bool>(sweeps[Swpit].idx, sweeps[Swpit].dir))));
}
// Insert Lines
int StartInSweep;
for(StartInSweep = Swpit; Swpit < sz(sweeps) && sweeps[Swpit].y == (*Yit); Swpit++) {
XSweep.insert(pair<int, pair<int, bool> >(sweeps[Swpit].x, pair<int, bool>(sweeps[Swpit].idx, sweeps[Swpit].dir)));
}
// Make Cutable Lines
set<pair<int, pair<int, bool> > >::iterator it, ittmp;
for(int i = StartInSweep; i < Swpit; i++) {
ittmp = it = XSweep.find(pair<int, pair<int, bool> >(sweeps[i].x, pair<int, bool>(sweeps[i].idx, sweeps[i].dir)));
// Right Direction
if(!(*it).second.second) { ittmp++; InsertHubo(points, dlenR, hubos, (*it).second.first, (*ittmp).second.first); }
// Left Direction
else { ittmp--; InsertHubo(points, dlenR, hubos, (*ittmp).second.first, (*it).second.first); }
}
}
}
// 실제 정답인 HuboLine 생성 함수
// points : Reindexed 필요
void MakeRealAns(const vector<Point>& points, const vector<ll>& dlenR, vector<HuboLine>& hubos) {
vector<HuboLine> mayhubo; MakeHubo(points, dlenR, mayhubo);
for(int i = 0; i < sz(mayhubo); i++) {
if(CheckSplitLineIsAnswer(points, mayhubo[i])) {
hubos.pb(mayhubo[i]); return;
}
}
}
int main() {
Input(Points);
Reindexed(Points); MakeDP_dlenR(Points, DlenR); MakeRealAns(Points, DlenR, HuboLines);
if(!HuboLines.empty()) return printf("%d %d %d %d\n", HuboLines[0].x0, HuboLines[0].y, HuboLines[0].x1, HuboLines[0].y) * 0;
DlenR.clear(); Reflect(Points); Reindexed(Points); MakeDP_dlenR(Points, DlenR); MakeRealAns(Points, DlenR, HuboLines);
if(!HuboLines.empty()) return printf("%d %d %d %d\n", HuboLines[0].y, HuboLines[0].x0, HuboLines[0].y, HuboLines[0].x1) * 0;
printf("NO\n");
return 0;
}