POJ 1788 Building a New Depot(计算正多边形边长)
http://poj.org/problem?id=1788
题意: ZOJ 2157
有一个多边形(可能是凹或凸),这个多边形的每条边都平行于坐标轴,且给出多边形所有顶点的坐标,每个顶点都是拐点(即连接该顶点的两边肯定相互垂直),现在要你输出该多边形的周长.
分析:
由于题目给出的该多边形的限制条件:平行坐标轴,每个点都是拐点. 那么可以得出结论:
对于每个X或Y坐标,该坐标上多边形的顶点数目一定是偶数个.(假设x=5坐标有多个顶点,那么顶点数一定是偶数,比如2个或4个或6个,不可能是奇数个)
对于某个坐标值X(或Y),如果该坐标值有偶数个点,那么该坐标上肯定有边,且从上到下相邻的两个点互连成边.如下图:
对于上图,可以自己对于用例画画,验证一下.
由上面两条结论,我们可以知道每个有多边形点的x或y坐标的边构造必然是: 坐标相邻的两个点连接成一条边即可,所以我们只要加上所有这些边即可.
首先把所有点坐标按X值排序,算出同一X值上的所有竖直的边长.
然后把所有点坐标按Y值排序,算出同一Y值上的所有水平的边长.
所有边长相加输出周长即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
struct Point
{
int x,y;
}P[maxn];
bool compare_x(Point A,Point B)//升序排列
{
return A.x<B.x || (A.x==B.x&&A.y<B.y);
}
bool compare_y(Point A,Point B)
{
return A.y<B.y || (A.y==B.y&&A.x<B.x);
}
int main()
{
int n;
while(scanf("%d",&n)==1 && n)
{
for(int i=0;i<n;++i) scanf("%d%d",&P[i].x,&P[i].y);
int ans=0;
sort(P,P+n,compare_x);
for(int i=0;i<n;)
{
if(P[i].x==P[i+1].x)//计算竖直边
{
ans += P[i+1].y-P[i].y;
i+=2;
}
else ++i;
}
sort(P,P+n,compare_y);
for(int i=0;i<n;)
{
if(P[i].y==P[i+1].y)//计算水平边
{
ans+= P[i+1].x-P[i].x;
i+=2;
}
else ++i;
}
printf("The length of the fence will be %d units.\n",ans);
}
return 0;
}
分享到:
相关推荐
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj 2749 Building roads.md
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1942-Paths on a Grid 解题报告+AC代码
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ初级-计算几何学 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要...当然,我们希望得到的小段越长越好,你的任务是计算能够得到的小段木头的最大长度。