Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次在POJ上写评论,为大家双手递上源码

Posted by vjubge4 at 2019-04-03 22:44:44 on Problem 3293
// 简单说一下这个题,能满足题意需要3个条件
// 第一:行列平面扫描时每行必有偶数个点,这偶数个点两两形成边
// 第二:根据题里的要求 这些边不能相交
// 第三:很容易被忽略的,要围成的图形应只有1个连通分量,也就是说需要沿着边走一圈,应该有N个点,若少于N个则不成立
// 希望能帮上大家,谢谢
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
struct Point{
    int x, y;
    int edge_h, edge_v;
    int id;
}Ps[100016];
bool comp1(Point a, Point b){
    if(a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}
bool comp2(Point a, Point b){
    if (a.y == b.y){
        return a.x < b.x;
    }
    return a.y < b.y;
}
bool comp3(Point a, Point b){
    return a.id < b.id;
}
int N;
int main(){
    int Num;
    scanf("%d", &Num);
    for (int num = 0; num < Num; ++num) {
        scanf("%d", &N);
        for (int i = 0; i < N; ++i) {
            scanf("%d %d",&Ps[i].x, &Ps[i].y);
            Ps[i].id = i;
        }
        vector<pair<int, int> > linx;
        vector<pair<int, int> > liny;
        int res = 0;
        sort(Ps, Ps + N, comp1);
        bool able = true;
        for (int i = 0; i < N; ++i) {
            if (Ps[i].x == Ps[i + 1].x){
                liny.push_back(make_pair(Ps[i].id, Ps[i + 1].id));
                Ps[i + 1].edge_v = Ps[i].edge_v = liny.size() - 1;
                res += Ps[i + 1].y - Ps[i].y;
                i++;
            } else {
                able = false;
                break;
            }
        }
        if (!able){
            printf("-1\n");
            continue;
        }

        sort(Ps, Ps + N, comp2);
        for (int i = 0; i < N; ++i) {
            if (Ps[i].y == Ps[i + 1].y){
                linx.push_back(make_pair(Ps[i].id, Ps[i + 1].id));
                Ps[i + 1].edge_h = Ps[i].edge_h = linx.size() - 1;
                res += Ps[i + 1].x - Ps[i].x;
                i++;
            }else {
                able = false;
                break;
            }
        }
        if (!able){
            printf("-1\n");
            continue;
        }

        sort(Ps, Ps + N, comp3);
        for (int i = 0; i < linx.size(); ++i) {
            for (int j = 0; j < liny.size(); ++j) {
                if (Ps[linx[i].first].x < Ps[liny[j].first].x && Ps[linx[i].second].x > Ps[liny[j].first].x
                && Ps[liny[j].first].y < Ps[linx[i].first].y && Ps[liny[j].second].y > Ps[linx[i].first].y){
                    able = false;
                    break;
                }
            }
            if(!able){
                break;
            }
        }
        if (!able){
            printf("-1\n");
            continue;
        }

        int go_y = true;
        int ctr = 0;
        int next = 0;
        while (true){
            ctr ++;
            if (go_y){
                int a = liny[Ps[next].edge_v].first;
                int b = liny[Ps[next].edge_v].second;
                next = next == a ? b : a;
            } else {
                int a = linx[Ps[next].edge_h].first;
                int b = linx[Ps[next].edge_h].second;
                next = next == a ? b : a;
            }
            go_y = !go_y;
            if (next == 0){
                break;
            }
        }
        if (ctr != N){
            printf("-1\n");
        } else {
            printf("%d\n", res);
        }
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator