Dog and Gopher

Dog and Gopher

时间: 1ms        内存:64M

描述:

A large field has a dog and a gopher. The dog wants to eat the gopher, while the gopher wants to run to safety through one of several gopher holes dug in the surface of the field.

Neither the dog nor the gopher is a math major; however, neither is entirely stupid. The gopher decides on a particular gopher hole and heads for that hole in a straight line at a fixed speed. The dog, which is very good at reading body language, anticipates which hole the gopher has chosen. The dog heads at double the speed of the gopher to the hole. If the dog reaches the hole first, the gopher gets gobbled up; otherwise, the gopher escapes.

You have been retained by the gopher to select a hole through which it can escape, if such a hole exists.

输入:

The first line of input contains four floating point numbers: the (x,y) coordinates of the gopher followed by the (x,y) coordinates of the dog. Subsequent lines of input each contain two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in metres, to the nearest mm.

输出:

Your output should consist of a single line. If the gopher can escape the line should read "The gopher can escape through the hole at (x,y)." identifying the appropriate hole to the nearest mm. Otherwise the output line should read "The gopher cannot escape." If the gopher may escape through more than one hole, choose the first one in the input. If the gopher and dog reach the hole at the same time, the gopher gets gobbled. There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000.

示例输入:

1.000 1.000 2.000 2.000
1.500 1.500

示例输出:

The gopher cannot escape.

提示:

参考答案(内存最优[800]):

#include<stdio.h>
inline double doub(double x,double y)
{
	return (x-y)*(x-y);
}
int main()
{
	double gx,gy,dx,dy;
	while(scanf("%lf%lf%lf%lf",&gx,&gy,&dx,&dy)==4)
	{
		double x,y,resx,resy;
		bool sign=0;
		while(scanf("%lf%lf",&x,&y)==2)
			if(!sign&&4*(doub(gx,x)+doub(gy,y))<=doub(dx,x)+doub(dy,y))
			{
				resx=x;resy=y;
				sign=1;
			}
		if(sign)
			printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",resx,resy);
		else
			printf("The gopher cannot escape.\n");
		break;
	}
	return 0;
}

参考答案(时间最优[0]):

#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct point
{
    double x,y;
    int id;
};
point hole,ans,dog,gopher;
const double eps = 1e-6;
void dist(point hole,double &todog,double &togop)
{
    todog =sqrt((dog.x - hole.x)*(dog.x - hole.x)+(dog.y-hole.y)*(dog.y-hole.y));
    togop = sqrt((gopher.x - hole.x)*(gopher.x - hole.x)+(gopher.y-hole.y)*(gopher.y-hole.y));
}
char str[100];
int main()
{
    while( ~scanf("%lf %lf %lf %lf\n",&gopher.x,&gopher.y,&dog.x,&dog.y))
    {
        int flag  = 1;
        double todog,togop;
        while(gets(str))
        {
            if( strlen(str)==0)break;
            sscanf(str,"%lf%lf",&hole.x,&hole.y);
            dist(hole,todog,togop);
            if( flag && togop < todog *0.5)
            {
                printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",hole.x,hole.y);
                flag = 0;
            }
        }
        if(flag)puts("The gopher cannot escape.");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注