Submission #18451

#	Time	Username	Problem	Language	Result	Execution time	Memory
18451		youngyojun	Demarcation (BOI14_demarcation)	C++98	0 / 100	9 ms	2944 KiB

demarcation

#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;
}

Compilation message (stderr)

demarcation.cpp: In function 'void Input(std::vector<Point>&)':
demarcation.cpp:48:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, x, y; scanf("%d", &N);
                                 ^
demarcation.cpp:49:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < N; scanf("%d%d", &x, &y), points.pb(Point(x, y)), i++);
     ^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50