11796 - Dog Distance

[zholnin]

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";
}