Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一次在POJ上写评论,为大家双手递上源码// 简单说一下这个题,能满足题意需要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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator