HOJ13832 Fence

野性酷女 2022-06-10 00:52 198阅读 0赞

<table style="font-family:Tahoma"> 
 <tbody> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Problem description</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">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.</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Input</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">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&nbsp;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.</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Output</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">It is clear that the perimeter length of any fence built over the edges and diagonals of the grid can be uniquely written as<img src="http://acm.hnu.cn/online/images/13832.bmp" alt="">&nbsp;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&nbsp;<img src="http://acm.hnu.cn/online/images/13832.bmp" alt="">. 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.</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Sample Input</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt"> <pre>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</pre> </td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Sample Output</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt"> <pre>12 6
0 4</pre> </td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Problem Source</td> 
 </tr> 
 <tr> 
 <td style="font-family:Tahoma; font-size:9pt">Asia Region, Tehran Site,Sharif University of Technology, 24?25 December 2015</td> 
 </tr> 
 </tbody> 
</table>

题意剖析：即给出点的坐标，求最小凸包（凸包是什么？自行百度），其中这里的凸包有限制，即只能沿平行于坐标轴或正方形对角线走。最后求凸包的周长，表示为![13832.bmp][]，输出a和b。

思路：如果求最小凸包时同时考虑其限制条件，会让这道题变复杂。我们不妨先用Andrew算法（不懂？？自己百度）求出最小凸包

，记录构成最小凸包的点是哪些。最后把前后两个点依次取出，根据限制特殊化处理其周长问题！

AC代码如下：

#include<iostream>
 #include<string>
 #include<vector>
 #include<string.h>
 #include<set>
 #include<algorithm>
 #include<queue>
 #include<map>
 #include<stdio.h>
 #include<math.h>
 using namespace std;
 
 struct Points{
 long long x;
 long long y;
 };
 struct Points point[10005],result[10005];//result用来记录构成凸包的点
 long long n,a,b;
 
 bool Compare(struct Points a,struct Points b){
 if(a.x<b.x){
 return true;
 }else if(a.x==b.x&&a.y<b.y){
 return true;
 }else{
 return false;
 } 
 }
 
 bool Cross(struct Points p1,struct Points p2,struct Points q1){//用来判断两线段的相对位置
 if(((p1.x-q1.x)*(p2.y-q1.y)-(p2.x-q1.x)*(p1.y-q1.y))<=0)
 return true;
 else
 return false;
 }

//Andrew算法核心代码
 long long ConvexHull(struct Points *p,long long n,struct Points *ch){
 sort(p,p+n,Compare);
 long long m=0;
 for(int i=0;i<n;i++){
 while(m>1&&Cross(p[i],ch[m-1],ch[m-2]))m--;
 ch[m++]=p[i];
 }
 int k=m;
 for(int i=n-2;i>=0;i--){
 while(m>k&&Cross(p[i],ch[m-1],ch[m-2]))m--;
 ch[m++]=p[i];
 }
 if(n>1)m--;
 return m;
 }
 int main()
 {
 cin.sync_with_stdio(false);//这个可忽略，只是用来减低时间复杂度的小操作
 while(cin>>n&&n){
 a=0;b=0;
 for(int i=0;i<n;i++){
 cin>>point[i].x>>point[i].y;
 }
 long long pp=ConvexHull(point,n,result);
 /* cout<<pp<<endl;
 for(int i=0;i<=pp;i++){
 cout<<result[i].x<<" "<<result[i].y<<endl;
 }*/

//计算周长
 for(int i=0;i<pp;i++){
 if(result[i].x==result[i+1].x){
 // cout<<"1"<<endl;
 a+=abs(result[i].y-result[i+1].y);
 }else if(result[i].y==result[i+1].y){
 // cout<<"2"<<endl;
 a+=abs(result[i].x-result[i+1].x); 
 }else if(abs(result[i].x-result[i+1].x)==abs(result[i].y-result[i+1].y)){
 // cout<<"3"<<endl;
 b+=abs(result[i].x-result[i+1].x);
 }else{
 // cout<<"4"<<endl;
 b+=min(abs(result[i].x-result[i+1].x),abs(result[i].y-result[i+1].y));
 a+=abs(abs(result[i].x-result[i+1].x)-abs(result[i].y-result[i+1].y));
 }
 // cout<<a<<" "<<b<<endl;
 }
 cout<<a<<" "<<b<<endl;
 }
 return 0;
 }

时间复杂度为O（2nlog(n))，一次AC！

[13832.bmp]: http://acm.hnu.cn/online/images/13832.bmp