2013
12-23

# Rectangular Polygons

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.

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| ≤ 10 000.

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.

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.

4
0 0
2 2
0 2
2 0

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

0

NESW
WNESWN

HintThe second sample  input corresponds  to the picture.  

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。