首页 > 代码库 > POJ 1788 Building a New Depot 解题报告
POJ 1788 Building a New Depot 解题报告
Description
Advanced Cargo Movement, Ltd. is successfully expanding. In order to meet new demands on truck maintenance, the management of the company decided to build a new truck depot. A suitable lot for building a depot was purchased and a construction company ``Masonry and Fences for Future, Ltd.‘‘ was hired to build a depot.
The area of the depot will be enclosed by a fence. The fence is supposed to enclose a connected area of a lot and each part of the fence follows North-South or East-West direction. At each place where the fence changes its direction, there is a single post. The posts are only at points where the fence changes the direction, i.e., there are no unnecessary posts. When MFF workers have built all of the posts, they lost the plan of a depot being built. At this moment, they asked you for a help.
Given the coordinates of all the posts, your task is to compute the length of the fence.
The area of the depot will be enclosed by a fence. The fence is supposed to enclose a connected area of a lot and each part of the fence follows North-South or East-West direction. At each place where the fence changes its direction, there is a single post. The posts are only at points where the fence changes the direction, i.e., there are no unnecessary posts. When MFF workers have built all of the posts, they lost the plan of a depot being built. At this moment, they asked you for a help.
Given the coordinates of all the posts, your task is to compute the length of the fence.
Input
The input consists of several blocks. The first line of each block contains a single number P, 1 <= P <= 100 000. P is the number of posts which have been built. Each of the following P lines contains two integers X and Y, 0 <= X, Y <= 10 000, which represent coordinates of the posts in MFF internal units (which no one else is able to understand). No two posts have the same coordinates.
Each block is followed by a single empty line and the input is terminated by a line containing a single number 0.
Each block is followed by a single empty line and the input is terminated by a line containing a single number 0.
Output
Output contains a single line for each block. The line should contain the text "The length of the fence will be L units.", where L is replaced by an actual length of the fence. You can assume that the fence can always be built.
Sample Input
61 11 33 32 13 22 20
Sample Output
The length of the fence will be 8 units.
题目大意:就是数字是柱子的坐标,没两根柱子之间有栅栏 求栅栏的长度。。。
解题思路:两次排序 第一次按X排,第二次按y排,,,,然后分别把差值加起来
1 #include<stdio.h> 2 #include<algorithm> 3 #include<math.h> 4 using namespace std; 5 struct weizhi{ 6 int x; 7 int y; 8 }a[200000]; 9 bool cmp1(weizhi a,weizhi b)10 {11 if(a.x==b.x)12 return a.y<b.y;13 return a.x<b.x;14 }15 bool cmp2(weizhi a,weizhi b)16 {17 if(a.y==b.y)18 return a.x<b.x;19 return a.y<b.y;20 }21 int main()22 {23 long int n;24 while(scanf("%d",&n)!=EOF)25 {26 if(n==0)break;27 int i;28 for(i=0;i<n;i++)29 {30 scanf("%d %d",&a[i].x,&a[i].y);31 }32 int sum=0;33 sort(a,a+n,cmp1);34 for(i=0;i<n;i+=2)35 {36 sum+=a[i+1].y-a[i].y;37 }38 sort(a,a+n,cmp2);39 for(i=0;i<n;i+=2)40 {41 sum+=a[i+1].x-a[i].x;42 }43 printf("The length of the fence will be %d units.\n",sum);44 }45 return 0;46 }
POJ 1788 Building a New Depot 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。