| Fence |
| Time Limit: 10000ms, Special Time Limit:25000ms, Memory Limit:65536KB |
| Total submit users: 6, Accepted users: 5 |
| Problem 13832 : No special judgement |
| Problem description |
| M-O (Microbe-Obliterator) is a tiny robot, programmed to clean any microbes it detects in the Axiom, a starliner spacecraft built by the Buy n Large (BNL) corporation. Tonight M-O is too busy since the great hall of the Axiom is a mess. A number of foreign microbes have attacked the spacecraft and are spread on the floor of the great hall. It’s M-O’s duty to wipe all those microbes. The floor of the great hall is an infinite grid of 1×1 cells. The 4 edges and the 2 diagonals of each cell are drawn as white segments. The microbes are currently located only on the corners of the cells. Since the cleaning job might take a lot of time, M-O needs to build a protector fence around the microbes as soon as possible, to keep the Axiom residents safe and to prevent the microbes from spreading to the other areas of the spacecraft. Since M-O is very regular, it makes the fence as a single closed region with borders only on the white segments (cell edges and diagonals). All microbes should be located inside the fence, or on its borders. Given the map of the microbes, your task is to help M-O build a fence with the minimum perimeter. |
| Input |
| There are multiple test cases in the input. Each test case starts with a line containing a single integer n, the number of microbes in the great hall (0 ⩽ n ⩽ 10000). Each of the next n lines contains two integers xi and yi, denoting the coordinates of the i-th microbe. The absolute value of all coordinates is guaranteed to be at most 106. The coordinates are reported based on some arbitrary grid cell corner, taken as the coordinates origin. The input terminates with a line containing a single zero, which should not be considered as a test case. |
| Output |
It is clear that the perimeter length of any fence built over the edges and diagonals of the grid can be uniquely written as where a and b are two non-negative integer numbers. For each test case, write a single line containing the two integers a and b with the assumption that the perimeter length of the fence with the minimum perimeter is . Note that a fence must be seen as a closed path; therefore if two parts of the fence overlap, the overlapped part must be taken into account twice. |
| Sample Input |
11 2 2 3 2 3 0 7 1 3 5 1 4 7 4 5 4 0 2 7 2 2 0 2 1 3 3 1 0 |
| Sample Output |
12 6 0 4 |
题意：给定一些点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来，要走完这个多边形，并且只能走直线或者对角线，最后输出最短走直线的长度和对角线的长度。（给定1*1的格子）。比赛的时候没有看懂输出格式啊，就很难过，不然理论可以ac的。
题解：也就是求凸包了，找出这些构成凸包的点，求出走这些点的直线长度和对角线长度。
求凸包：先找出最左下的点，作为基点，这个点肯定在凸包上。然后再将其他点进行排序，从下往上，从左向右依次访问。计算叉积，如果是左拐则将该目前点入栈，如果是右拐，则出栈，依次进行，访问到最后一个点。
详见代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; int n; #define Vector Point struct Point { double x,y; inline Point(double x=0,double y=0):x(x),y(y) {} }p[10000+5],ch[10000+5]; bool cmp(Point A, Point B) { if(A.x != B.x) return A.x < B.x; else return A.y < B.y; } Vector operator - (Vector A, Vector B) {return Vector(A.x - B.x, A.y - B.y);} inline double Cross(Vector A, Vector B)//叉积 { return A.x * B.y - A.y * B.x; } int ConvexHull() { sort(p,p+n,cmp); int m = 0; for(int i = 0; i <n; i++) { while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;//如果发现更好的点把之前凸包内的点吐出 ch[m++] = p[i]; } int k = m; for(int i = n-2; i >= 0; i--) { while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; ch[m++] = p[i]; } if(n > 1) m--; return m; } int main() { int m; // freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); while(scanf("%d",&n),n){ for(int i = 0; i < n; i++) { int a,b; cin>>a>>b; p[i] = Point(a,b); } m = ConvexHull(); int aa=0,bb=0; for(int i=0;i<m;i++) { int x=abs(ch[i].x-ch[i+1].x),y=abs(ch[i].y-ch[i+1].y); if(x>y) { aa+=x-y; bb+=y; } else if(x==y) bb+=y; else { aa+=y-x; bb+=x; } } printf("%d %d ",aa,bb); } }