UVALive 3959 Rectangular Polygons （排序贪心）

Rectangular Polygons

题目链接：

http://acm.hust.edu.cn/vjudge/contest/129733#problem/G

Description

In this problem, we will help the Faculty of Civil Engineering. They need a software to analyze ground plans of buildings. Specifically, your task is to detect outlines of a building when all of its corners are given. You may assume that each building is a rectangular polygon with each of its sides being parallel either with X or Y axis. Therefore, each of its vertex angles is exactly either 90 or 270 degrees.

Input

The input contains several buildings. The description of each building starts with a single positive integer N , the number of corners (polygon vertices), 1 <= N <= 1000 . Then there are N pairs of integer numbers Xi, Yi giving coordinates of individual corners, | Xi|,| Yi| <= 10000 . You may assume that all corners are listed and no two of them have the same coordinates. The polygon does always exist, it is closed, its sides do not intersect or touch (except neighboring sides, of course), and it contains no "holes" inside. In other words, the outline is formed by one closed line. The order of corners in the input file may be arbitrary. There is an empty line after each building, then the next one is described. After the last building, there is a single zero that signals the end of input.

Output

For each building, output one line containing N characters without any whitespace between them. The characters should be uppercase letters that specify directions of individual walls (sides) when the building outline is followed. " N" stands for North (the positive direction of the Y axis), `` E" for East (the positive direction of the X axis), "W" for West, and " S" for South. The "walk" should start in the vertex that has been given first in the input and always proceed in the clockwise direction.

Sample Input

4 0 0 2 2 0 2 2 0 6 1 1 2 2 0 1 1 0 0 2 2 0 0

Sample Output

NESW WNESWN

Source

2016-HUST-线下组队赛-2
##题意：给出平面上N个点，构造一个每条边都平行于轴的多边形. 从起点#1开始顺时针输出行进方向.
##题解：观察结果图形：所有边一定平行轴. 那么对于y坐标相同的若干点#1~#m，有若干推论：（均可以反证）首先，m的一定是偶数，否者多出来的点不能正常连边. 然后，这m个点一定有 m/2 条边，否则剩下的边不能正常连边. 最后，这m个点的连边方式一定是：(1,2),(3,4)...(m-1,m)，否则会出现交叉或多余点. 对于x坐标相同的点也是如此. 对所有点按x为第一优先级排序后，可以将所有竖边连起来；同理得到所有横边.
现在已经得到关于最后结果的图模型，问题是怎么按要求输出：直接按从#1开始或许有点麻烦，这里可以从最左上角的点开始往右走，这样保证了输出的轨迹一定是顺时针. 当遍历到#1时才开始输出，计数n次输出即结束. 所以最多遍历2次.
这题瞎搞了两小时，写了160+行结果TLE... 赛时想得太复杂，各种xjb删点删边瞎搞一通. 今天真是打得太挫了，2个小时写两题，后面的时间都在搞一个题. 两个人搞还是有点蛋疼，有几道比较简单的题都没开.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 1010 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

int n;
struct Point {
int id;
int x, y;
}p[maxn];
int g[maxn][4];

bool cmp1(Point a, Point b) {
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
bool cmp2(Point a, Point b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}

int main(int argc, char const *argv[])
{
//IN;

while(scanf("%d", &n) != EOF && n)
{
    memset(g, 0, sizeof(g));
    int cur = 0, cx = inf, cy = -inf; //top-left most
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &p[i].x,&p[i].y);
        p[i].id = i;
        if(p[i].y > cy) cx = p[i].x, cy = p[i].y, cur = i;
        if(p[i].y == cy && p[i].x < cx) cx = p[i].x, cur = i;
    }

    sort(p+1, p+1+n, cmp1);
    for(int i=1; i<=n; i+=2) {
        g[p[i].id][1] = p[i+1].id;
        g[p[i+1].id][3] = p[i].id;
    }

    sort(p+1, p+1+n, cmp2);
    for(int i=1; i<=n; i+=2) {
        g[p[i].id][0] = p[i+1].id;
        g[p[i+1].id][2] = p[i].id;
    }

    int order = 0;
    bool flag = 0;
    int cnt = 0;
    while(1) {
        if(cur == 1) flag = 1;

        char ans = 0;
        int tmp = cur;
        if(!order) {
            if(g[tmp][1]) cur = g[tmp][1], ans = 'E';
            if(g[tmp][3]) cur = g[tmp][3], ans = 'W';
        } else {
            if(g[tmp][0]) cur = g[tmp][0], ans = 'N';
            if(g[tmp][2]) cur = g[tmp][2], ans = 'S';
        }
        order = !order;

        if(flag) putchar(ans), cnt++;
        if(cnt >= n) break;
    }
    putchar('
');
}

return 0;

}