10473 맞왜틀

Source.cpp

#include <stdio.h>
#include <queue>
#include <math.h>
#include <algorithm>

struct point
{
	double x;
	double y;
};

struct element
{
	int index;
	double time;
	element(int index, double time) : index(index), time(time) {}
};

bool operator<(const element &a, const element &b)
{
	return (a.time > b.time);
}

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

int main()
{
	for (int testcase = 1; testcase < 100; testcase++)
	{
		char input_file_name[20], output_file_name[20];
		FILE *fin, *fout;
		sprintf(input_file_name, "generated%03d.in", testcase);
		sprintf(output_file_name, "generated%03d.ans", testcase);
		fin = fopen(input_file_name, "r");
		fout = fopen(output_file_name, "r");
		point st, ed, cannon[100];
		int n;
		double time[100], answer;
		bool visit[100] = {};
		std::priority_queue<element> pq;
		fscanf(fin, "%lf %lf %lf %lf %d", &st.x, &st.y, &ed.x, &ed.y, &n);
		answer = dist(st, ed) / 5.0;
		for (int i = 0; i < n; i++)
		{
			fscanf(fin, "%lf %lf", &cannon[i].x, &cannon[i].y);
			time[i] = dist(st, cannon[i]) / 5;
			pq.push(element(i, time[i]));
		}
		while (!pq.empty())
		{
			double cur_time = pq.top().time;
			int index = pq.top().index;
			pq.pop();
			if (visit[index]) continue;
			visit[index] = true;
			time[index] = cur_time;
			for (int i = 0; i < n; i++)
			{
				if (i == index || visit[i]) continue;
				double temp_time = cur_time + std::min(2.0 + abs(50.0 - dist(cannon[index], cannon[i])) / 5.0, dist(cannon[index], cannon[i]) / 5.0);
				if (temp_time < time[i])
				{
					time[i] = temp_time;
					pq.push(element(i, time[i]));
				}
			}
		}
		for (int i = 0; i < n; i++)
		{
			double temp_time = time[i] + std::min(2.0 + abs(50.0 - dist(cannon[i], ed)) / 5.0, dist(ed, cannon[i]) / 5.0);
			if (temp_time < answer) answer = temp_time;
		}
		double tc_answer;
		fscanf(fout, "%lf", &tc_answer);
		if (abs(tc_answer-answer) >= 0.001)
		{
			printf("%d 케이스에서 틀림.\n", testcase);
			printf("오답 : %f\n", answer);
			printf("정답 : %f\n", tc_answer);
		}
		//printf("%f\n", answer);
	}
	return 0;
}