11796 - Dog Distance

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
zholnin
New poster
Posts: 8
Joined: Thu Aug 21, 2014 12:03 am

Re: 11796 - Dog Distance

Post by zholnin » Tue Sep 22, 2015 12:28 am

Can somebody say anything about below? I think I can change it slightly to improve precision, but through random testing I went through hundreds and hundreds of testcases and didn't have any differences compared to uDebug.

Either I have some very stupid mistake, or authors of this problem actually fished for one specific testcase where rounding would make difference and change something like 42.4999999999999 vs 42.5000000000001 difference into full fledged error.

Doesn't seem to be very nice way of making problems, if this is the case.

Code: Select all


#define _USE_MATH_DEFINES
#include <vector>
#include <list>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <map>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <assert.h>
#include <bitset>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);

	clock_t start = clock();
	
	int t, tc = 1;
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		int A, B;
		cin >> A >> B;
		vector<pair<double, double>> Adots;
		vector<pair<double, double>> Bdots;
		vector<double> Atimes;
		vector<double> Btimes;

		for (int i = 0; i < A; i++)
		{
			double x, y;
			cin >> x >> y;
			if (Atimes.size() == 0) Atimes.push_back(0.0);
			else
			{
				double distance = Atimes.back() + sqrt((Adots.back().first - x)*(Adots.back().first - x) + (Adots.back().second - y)*(Adots.back().second - y));
				Atimes.push_back(distance);
			}
			Adots.push_back({ x, y });
		}

		for (int i = 0; i < B; i++)
		{
			double x, y;
			cin >> x >> y;
			if (Btimes.size() == 0) Btimes.push_back(0.0);
			else
			{
				double distance = Btimes.back() + sqrt((Bdots.back().first - x)*(Bdots.back().first - x) + (Bdots.back().second - y)*(Bdots.back().second - y));
				Btimes.push_back(distance);
			}
			Bdots.push_back({ x, y });
		}

		for (int i = 0; i < A; i++) Atimes[i] /= Atimes.back();
		for (int i = 0; i < B; i++) Btimes[i] /= Btimes.back();

		int iA = 0, iB = 0; 
		double time = 0.0;
		double maxD = 0.0;
		double minD = 10000.0;
		while (iA + 1 < A && iB + 1 < B)
		{
			double Ax1 = Adots[iA + 1].first;
			double Ax0 = Adots[iA].first;
			double Ay1 = Adots[iA + 1].second;
			double Ay0 = Adots[iA].second;
			double At1 = Atimes[iA + 1];
			double At0 = Atimes[iA];

			double Bx1 = Bdots[iB + 1].first;
			double Bx0 = Bdots[iB].first;
			double By1 = Bdots[iB + 1].second;
			double By0 = Bdots[iB].second;
			double Bt1 = Btimes[iB + 1];
			double Bt0 = Btimes[iB];

			double xA = (Ax0 * (At1 - time) + Ax1 * (time - At0)) / (At1 - At0);
			double yA = (Ay0 * (At1 - time) + Ay1 * (time - At0)) / (At1 - At0);

			double xB = (Bx0 * (Bt1 - time) + Bx1 * (time - Bt0)) / (Bt1 - Bt0);
			double yB = (By0 * (Bt1 - time) + By1 * (time - Bt0)) / (Bt1 - Bt0);

			double distance = sqrt((xA - xB)*(xA - xB) + (yA - yB)*(yA - yB));

			maxD = max(maxD, distance);
			minD = min(minD, distance);

			double dxA = ((Ax1 - Ax0) / (At1 - At0) - (Bx1 - Bx0) / (Bt1 - Bt0));
			double dyA = ((Ay1 - Ay0) / (At1 - At0) - (By1 - By0) / (Bt1 - Bt0));
			double dxB = ( - (Ax1 - Ax0) / (At1 - At0) * At0 + (Bx1 - Bx0) / (Bt1 - Bt0) * Bt0) + Ax0 - Bx0;
			double dyB = (-(Ay1 - Ay0) / (At1 - At0) * At0 + (By1 - By0) / (Bt1 - Bt0) * Bt0) + Ay0 - By0;

			if (abs(dyA) > 1e-12 || abs(dxA) > 1e-12)
			{


				double t = -(dxB * dxA + dyB * dyA) / (dxA * dxA + dyA * dyA);

				if (t >= max(At0, Bt0) && t <= min(At1, Bt1))
				{
					double distance = sqrt((dxA *t + dxB)*(dxA *t + dxB) + (dyA *t + dyB)*(dyA *t + dyB));
					maxD = max(maxD, distance);
					minD = min(minD, distance);
				}
			}

			if (Atimes[iA + 1] < Btimes[iB + 1]) iA++; else iB++;
			time = max(Atimes[iA], Btimes[iB]);
		}
		double xA = Adots.back().first;
		double yA = Adots.back().second;

		double xB = Bdots.back().first;
		double yB = Bdots.back().second;

		double distance = sqrt((xA - xB)*(xA - xB) + (yA - yB)*(yA - yB));

		maxD = max(maxD, distance);
		minD = min(minD, distance);
		
		cout << "Case " << tc << ": " << setprecision(0) << round(maxD - minD) << "\n";
	}

	clock_t end = clock();
//	cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << "\n";
}


Post Reply

Return to “Volume 117 (11700-11799)”