首页 > ACM题库 > HDU-杭电 > hdu 2440 Watch out the Animal-凸包问题-[解题报告]C++
2014
01-26

hdu 2440 Watch out the Animal-凸包问题-[解题报告]C++

Watch out the Animal

问题描述 :

There are n resting-places in the safari park. Some administrators are at the resting-places.Now we want to build a station in the park to guarantee that no animals run out of the park.Every two resting-places form a segment. If an animal runs accross a segment and thus will never be observed again, we say it is running out of the park. Lines of communication can be built between the station and a certain resting-place, but not between resting-places. Please calculate where the station should be built so that we will always know whether there are any animals running out of the park and at the same time minimize the length of the communication lines.

输入:

The first line of input contains a positive integer, N(5<=N<=100), the number of resting-places.N lines follow. Each gives the (x,y) coordinates (in mm) of a resting-place within the park. All coordinates are integers between 0 and 10,000.

输出:

The first line of input contains a positive integer, N(5<=N<=100), the number of resting-places.N lines follow. Each gives the (x,y) coordinates (in mm) of a resting-place within the park. All coordinates are integers between 0 and 10,000.

样例输入:

2

8
0 0
1453 6432
0 10000
9876 1234
10000 10000
8754 2345
10000 0
2465 6843

5
2 2
0 0
2 0
0 2
1 1

样例输出:

28284

6 

读懂了题的话就不难发现是要求费马点,不过输入点的顺序是不一定的,而且求的是凸包的费马点,不是所有点的费马点。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define eps 1e-10
using namespace std;

//hdu 2440
const int maxn = 111;
int n, T;
struct Point
{
    double x, y;
    Point (double x=0, double y=0):x(x), y(y) {}
}p[maxn], pt[maxn], ft;
typedef Point Vector;

Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }

bool operator < (const Point& a, const Point& b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

bool operator == (const Point& a, const Point& b)
{
    return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}

double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Angel(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }

int ConvexHull(Point *p, int n, Point* ch)//凸包
{
    sort(p, p+n);
    int m = 0;
    REP(i, n)
    {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    FD(i, n-2, 0)
    {
        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;
}

inline double dist(Point a, Point b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double fermat_point(Point *pt, int n, Point& ptres)
{
	Point u, v;
	double step = 0.0, curlen, explen, minlen;
	int i, j, k, idx;
	bool flag;
	u.x = u.y = v.x = v.y = 0.0;
	REP(i, n)
	{
		step += fabs(pt[i].x) + fabs(pt[i].y);
		u.x += pt[i].x;
		u.y += pt[i].y;
	}
	u.x /= n;
	u.y /= n;
	flag = 0;
	while(step > eps)
	{
		for(k = 0; k < 10; step /= 2, ++k)
			for(i = -1; i <= 1; ++i)
				for(j = -1; j <= 1; ++j)
				{
					v.x = u.x + step*i;
					v.y = u.y + step*j;
					curlen = explen = 0.0;
				        REP(idx, n)
					{
						curlen += dist(u, pt[idx]);
						explen += dist(v, pt[idx]);
					}
					if(curlen > explen)
					{
						u = v;
						minlen = explen;
						flag = 1;
					}
				}
	}
	ptres = u;
	return flag ? minlen : curlen;
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
	    scanf("%d", &n);
	    REP(i, n) scanf("%lf%lf", &p[i].x, &p[i].y);
	    int m = ConvexHull(p, n, pt);
	    double ans = fermat_point(pt, m, ft);
	    printf("%.0f\n", ans);
	    if(T > 0) puts("");
	}
	return 0;
}

解题转自:http://blog.csdn.net/diary_yang/article/details/11295261


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }