首页 > ACM题库 > HDU-杭电 > HDU 2907-Diamond Dealer-凸包问题-[解题报告]HOJ
2014
02-21

HDU 2907-Diamond Dealer-凸包问题-[解题报告]HOJ

Diamond Dealer

问题描述 :

Mr. Chou is the atworld diamond dealer. It is important that he knows the value of his (twodimensional) diamonds in order to be a succesful businessman. Mr. Chou is tired of calculating the values by hand and you have to write a program that makes the calculation for him.

Figure 2: Example diamond

The value of a diamond is determined by smoothness of its surface. This
depends on the amount of faces on the surface, more faces means a smoother surface. If there are dents (marked red in gure 2) in the surface of the diamond, the value of the diamond decreases. Counting the number of dents in the surface (a) and the number of faces on the surface that are not in dents (b), the value of the diamond is determined by the following formula: v = -a * p + b * q. When v is negative, the diamond has no value (ie. zero value).

输入:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
One line containing:
The cost for a dent in the surface of a diamond (0 <= p <= 100);
The value of a face in the surface of a diamond (0 <= q <= 100);
The number of vertices (3 <= n <= 30) used to describe the shape of the diamond.
n lines containing one pair of integers (-1000 <=xi,yi <= 1000) describing the surface of the diamond (x0,y0) – (x1,y1) -…..-(xn-1, yn-1) – (x0 ,y0) in clockwise order.
No combination of three vertices within one diamond will be linearly aligned.

输出:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
One line containing:
The cost for a dent in the surface of a diamond (0 <= p <= 100);
The value of a face in the surface of a diamond (0 <= q <= 100);
The number of vertices (3 <= n <= 30) used to describe the shape of the diamond.
n lines containing one pair of integers (-1000 <=xi,yi <= 1000) describing the surface of the diamond (x0,y0) – (x1,y1) -…..-(xn-1, yn-1) – (x0 ,y0) in clockwise order.
No combination of three vertices within one diamond will be linearly aligned.

样例输入:

1
10 5 7
0 10
8 4
10 -7
6 -9
-5 -4
-5 7
-2 6

样例输出:

15

http://acm.hdu.edu.cn/showproblem.php?pid=2907

参考了下别人的搜索代码~~

/*************************************************************************
	> File Name: main.cpp
	> Author: huangshuai
	> Mail: [email protected] 
	> Created Time: Wed 13 Mar 2013 08:45:03 AM CST
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
	int x,y;
	int num;
};
point vex[100];
int cross(const point &a,const point &b,const point &c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(const point &a,const point &b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(const point& a,const point &b)
{
	int m=cross(vex[0],a,b);
	if(m==0)
		return dis(vex[0],a)<dis(vex[0],b)?true:false;
	if(m>0)
		return true;
	else
		return false;
}
point stackk[100];
int flag[100],top,k;
void graham_scan(int n)
{
	int i;
	for(i=1;i<n;i++)
	{
		if(vex[i].y<vex[0].y||(vex[i].y==vex[0].y&&vex[i].x<vex[0].x))
		{
			point temp;
			temp=vex[0];
			vex[0]=vex[i];
			vex[i]=temp;
		}
	}
	sort(vex+1,vex+n,cmp);
	memset(stackk,0,sizeof(stackk));
	stackk[0]=vex[0];
	stackk[1]=vex[1];
	top=2;
	for(i=2;i<n;i++)
	{
		while(top>=2&&cross(stackk[top-2],stackk[top-1],vex[i])<0)
		{
			top--;
		}
		stackk[top++]=vex[i];
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,q,p;
		scanf("%d%d%d",&p,&q,&n);
		int i;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&vex[i].x,&vex[i].y);
			vex[i].num=i;
		}
		graham_scan(n);
	
		int ss=0;
		memset(flag,0,sizeof(flag));
		for(i=0;i<top;i++)
		{
			flag[stackk[i].num]=1;
		}
		flag[n]=flag[0];
		for(i=0;i<n;i++)
		{
			if(flag[i]==1&&flag[i+1]==0)
				ss++;
		}
		int res=top*q-ss*p-ss*q;
		if(res<=0)
			printf("0\n");
		else
			printf("%d\n",res);
	}
}

解题参考:http://blog.csdn.net/juststeps/article/details/8666769


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c