Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 6 KB
using System;
using System.Collections.Generic;
using System.IO;
namespace IndianaJones
{
class Program
{
public class Problem
{
public int n;
public Fal[] w;
public Problem(int n)
{
this.n = n;
w = new Fal[n];
}
}
public struct Fal
{
public int x, y, l;
public Fal(int x, int y, int l)
{
this.x = x; this.y = y; this.l = l;
}
public Pont Vege()
{
if (l > 0) return new Pont(x + l, y);
return new Pont(x, y - l);
}
public Pont Eleje()
{
return new Pont(x, y);
}
}
public struct Pont
{
public int x, y;
public Pont(int x, int y)
{
this.x = x;
this.y = y;
}
public long Tav(Pont other)
{
return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
}
}
public static List<Problem> problems = new List<Problem>();
public static Problem f;
public static long Tavolsag(Fal f1, Fal f2)
{
if ((f1.l == 0) && (f2.l == 0)) return f1.Eleje().Tav(f2.Eleje()) ;
if ((f1.l == 0) || (f2.l == 0))
{
if (f2.l == 0) { Fal f3 = f1; f1 = f2; f2 = f3; }
if (f2.l > 0)
{
if ((f1.x >= f2.Eleje().x) && (f1.x <= f2.Vege().x))
return (f1.y - f2.y) * (f1.y - f2.y);
}
else
{
if ((f1.y >= f2.Eleje().y) && (f1.y <= f2.Vege().y))
return (f1.x - f2.x) * (f1.x - f2.x);
}
}
if (f1.l * f2.l > 0)
{
if (f1.l > 0)
{
if (!((f1.Vege().x < f2.Eleje().x) || (f1.Eleje().x > f2.Vege().x)))
return (f1.y - f2.y) * (f1.y - f2.y);
}
else
{
if (!((f1.Vege().y < f2.Eleje().y) || (f1.Eleje().y > f2.Vege().y)))
return (f1.x - f2.x) * (f1.x - f2.x);
}
}
else
{
if (f1.l < 0) { Fal f3 = f1; f1 = f2; f2 = f3; }
if ((f1.Eleje().y <= f2.Vege().y) && (f1.Eleje().y >= f2.Eleje().y))
{
if ((f1.Eleje().x <= f2.x) && (f1.Vege().x >= f2.x)) return 0;
long d1 = f1.x - f2.x; d1 *= d1;
long d2 = f1.Vege().x - f2.x; d2 *= d2;
return Math.Min(d1, d2);
}
if ((f1.Eleje().x <= f2.x) && (f1.Vege().x >= f2.x))
{
if ((f1.Eleje().y <= f2.y) && (f1.Vege().y >= f2.y)) return 0;
long d1 = f1.y - f2.y; d1 *= d1;
long d2 = f1.y - f2.Vege().y; d2 *= d2;
return Math.Min(d1, d2);
}
}
long[] tt = new long[4];
tt[0] = f1.Eleje().Tav(f2.Eleje());
tt[1] = f1.Eleje().Tav(f2.Vege());
tt[2] = f1.Vege().Tav(f2.Eleje());
tt[3] = f1.Vege().Tav(f2.Vege());
Array.Sort(tt);
return tt[0];
}
public static double Munka()
{
long[,] tav = new long[f.n, f.n];
for (int i = 0; i != f.n; i++)
for (int j = i; j != f.n; j++)
{
tav[i, j] = Tavolsag(f.w[i], f.w[j]);
tav[j, i] = tav[i, j];
}
long[] d = new long[f.n]; for (int i = 0; i != f.n; i++) d[i] = long.MaxValue;
List<long> q = new List<long>(); q.Add(0); d[0] = 0;
while (q.Count > 0)
{
long b = q[0];
q.RemoveAt(0);
for (int i = 0; i != f.n; i++)
{
long dd = Math.Max(tav[b, i], d[b]);
if (dd < d[i])
{
d[i] = dd;
q.Add(i);
}
}
}
return d[1];
}
public static void Main(string[] args)
{
Beolvas("indiana.be");
double[] mo = new double[problems.Count];
for (int i = 0; i != mo.Length; i++) { f = problems[i]; mo[i] = Math.Sqrt(Munka()); };
Kiir("indiana.ki", mo);
}
public static void Kiir(string oup, double[] mo)
{
TextWriter tw = new StreamWriter(oup);
for (int i = 0; i != mo.Length; i++)
{
long r = (long)Math.Round(mo[i] * 100);
string s = r / 100 + ".";
r %= 100;
r += 100;
s += r.ToString().Remove(0, 1);
tw.WriteLine(s);
}
tw.Close();
}
public static void Beolvas(string inp)
{
TextReader tr = new StreamReader(inp);
string[] l;
int i = 0;
Problem p = null;
while (!(((l = tr.ReadLine().Split(' ')).Length == 1) && (l[0] == "0")))
{
if (l.Length == 1)
{
i = 0;
p = new Problem(int.Parse(l[0]));
problems.Add(p);
}
else
{
p.w[i] = new Fal(int.Parse(l[0]), int.Parse(l[1]), int.Parse(l[2]));
i++;
}
}
}
}
}
