Skip to content

Instantly share code, notes, and snippets.

@kinssang
Created Sep 26, 2017
Embed
What would you like to do?
10473 맞왜틀
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment