hdu 4717 이동 포인트(3 점)

http://acm.hdu.edu.cn/showproblem.php?pid=4717
대략적인 제목:각 점 의 좌표 와 각 점 의 이동 속도 와 방향 을 제시 합 니 다.그 시점 에서 가장 먼 거 리 를 모 으 는 것 이 모든 시간의 가장 먼 거리 에서 가장 작다 고 물 었 다.
경 기 를 할 때 줄곧 계산 기하학 이 라 고 생각 했 는데,선분 과 교차 하 는 것 과 관계 가 있다.경기 후 팀 원 들 은 이것 이 3 점 이 라 고 말 했다.곰 곰 이 생각해 보 니 확실히 3 점 이 었 다.그림 을 그 려 보 니 돌출 함수 로 가장 짧 은 거리 가 있 었 다.그리고 3 분 이면 돼.

#include <stdio.h>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

const int maxn = 310;
const int INF = 0x3f3f3f3f;

struct node
{
	double x,y,vx,vy;
}p[maxn],tp[maxn];
int n;
double mindis,time;
double dis(node a, node b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double cal(double t)
{
	for(int i = 1; i <= n; i++)
	{
		tp[i].x = p[i].x + t * p[i].vx;
		tp[i].y = p[i].y + t * p[i].vy;
	}
	double Max = -1.0;
	for(int i = 1; i < n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			double ans = dis(tp[i], tp[j]);
			if(Max < ans)
				Max = ans;
		}
	}
	return Max;
}

void solve()
{
	double low = 0, high = INF, mid,midmid;

	while(high - low > eps)
	{
		mid = (high + low)/2;
		midmid = (mid + high)/2;

		double ans1 = cal(mid);
		double ans2 = cal(midmid);

		if(ans1 > ans2)
			low = mid;
		else
			high = midmid;
	}
	time = low;
	mindis = cal(low);
}

int main()
{
	int test;
	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
			scanf("%lf %lf %lf %lf",&p[i].x, &p[i].y, &p[i].vx,&p[i].vy);
		solve();
		printf("Case #%d: %.2lf %.2lf
",item,time,mindis);
	}
	return 0;
}