battledev-ex5.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BattleDev
{
	public class Program
	{
		public class Current
		{
			public int Position { get; set; }

			public double Proba { get; set; }
		}

		public class Node
		{
			public int Index { get; set; }

			public Circle Circle { get; set; }

			public Node Parent { get; set; }

			public int Gain { get; set; }

			public List<Node> Children { get; set; }

			public Node(Circle c, int index)
			{
				Circle = c;
				Index = index;
				Children = new List<Node>();
			}
		}

		public class Circle
		{
			public int X { get; set; }
			public int Y { get; set; }
			public int R { get; set; }
			public int H { get; set; }
		}

		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());

			List<Node> nodes = new List<Node>();
			//List<Circle> circles = new List<Circle>();
			for (int i = 0; i < n; ++i)
			{
				string[] part = Console.ReadLine().Split(' ');
				nodes.Add(new Node(new Circle
				{
					X = int.Parse(part[0]),
					Y = int.Parse(part[1]),
					R = int.Parse(part[2]),
					H = int.Parse(part[3])
				}, i));
			}
			nodes.Add(new Node(new Circle
			{
				X = 0,
				Y = 0,
				H = 0,
				R = 10000000
			}, nodes.Count));

			n++;
			bool[,] hasPath = new bool[n,n];
			for(int i = 0 ; i < n ; ++i)
				for (int j = 0; j < n; ++j)
					hasPath[i, j] = true;

			for (int i = 0; i < nodes.Count; ++i)
			{
				Node inner = nodes[i];
				int minRadius = 100000000;
				Node container = null;
				for (int j = 0; j < nodes.Count; ++j)
				{
					if (i == j) continue;
					Node outer = nodes[j];
					if (IsIn(outer.Circle, inner.Circle))
					{
						if (minRadius > outer.Circle.R)
						{
							minRadius = outer.Circle.R;
							container = outer;
						}
					}
				}

				if (container != null)
				{
					for (int j = 0; j < n; ++j)
					{
						if (!IsIn(inner.Circle, nodes[j].Circle))
						{
						hasPath[inner.Index, j] = false;
							hasPath[j, inner.Index] = false;
						}
					}
					hasPath[inner.Index, container.Index] = true;
					hasPath[container.Index, inner.Index] = true;
				}
				hasPath[inner.Index, inner.Index] = false;
			}
			
			Queue<Node> tree = new Queue<Node>();
			tree.Enqueue(nodes.Last());

			while (tree.Any())
			{
				Node r = tree.Dequeue();
				int parent = r.Parent == null ? -1 : r.Parent.Index;
				for (int i = 0; i < n; ++i)
				{
					if (i == parent) continue;

					if (hasPath[r.Index, i])
					{
						Node child = nodes[i];
						r.Children.Add(child);
						child.Parent = r;

						tree.Enqueue(child);
					}
				}
			}

			Node root = nodes.Last();
			ExploreEdges(root, 0);

			
			int result = nodes.Max(node => node.Children.OrderByDescending(x => x.Gain).Take(2).Sum(x => x.Gain));

			Console.WriteLine(result);
		
		}

		static void ExploreEdges(Node root, int gain)
		{
			int max = 0;
			foreach (Node children in root.Children)
			{
				int cost = Math.Abs(root.Circle.H - children.Circle.H);

				ExploreEdges(children, cost);

				if (children.Gain > max)
				{
					max = children.Gain;
				}
			}

			root.Gain = gain + max;
		}

		static bool IsIn(Circle outer, Circle inner)
		{
			int maxR = outer.R;
			int minR = inner.R;

			double distance = Distance(outer, inner);
			return (distance + minR < maxR);
		}

		
		static double Distance(Circle c, Circle d)
		{
			return Math.Sqrt(Math.Pow(c.X - d.X, 2) + Math.Pow(c.Y - d.Y, 2));
		}
	}
}