Skip to content

Instantly share code, notes, and snippets.

@key-moon
Created Apr 6, 2019
Embed
What would you like to do?
static string Solve(string query)
{
ImageConverter converter = new ImageConverter();
var bmp = new Bitmap((Image)converter.ConvertFrom(Convert.FromBase64String(query)));
var uf = new UnionFind(bmp.Height * bmp.Width);
var whiteID = bmp.Height * bmp.Width - 1;
for (int i = 0; i < bmp.Height - 1; i++)
{
for (int j = 0; j < bmp.Width - 1; j++)
{
var id = (i * bmp.Width) + j;
if (bmp.GetPixel(j, i).B < 128)
{
if (bmp.GetPixel(j + 1, i).B < 128) uf.TryUnite(id, (i * bmp.Width) + (j + 1));
if (bmp.GetPixel(j, i + 1).B < 128) uf.TryUnite(id, ((i + 1) * bmp.Width) + j);
}
else
{
uf.TryUnite(id, whiteID);
}
}
}
for (int i = 0; i < bmp.Height; i++) if (bmp.GetPixel(bmp.Width - 1, i).B > 128) uf.TryUnite((i * bmp.Width) + (bmp.Width - 1), whiteID);
for (int i = 0; i < bmp.Width; i++) if (bmp.GetPixel(i, bmp.Height - 1).B > 128) uf.TryUnite(((bmp.Height - 1) * bmp.Width) + i, whiteID);
var dict = uf.AllRepresents.ToDictionary(x => x, _ => new List<Tuple<int, int>>());
for (int i = 0; i < bmp.Height; i++)
{
for (int j = 0; j < bmp.Width; j++)
{
var id = (i * bmp.Width) + j;
dict[uf.Find(id)].Add(new Tuple<int, int>(i, j));
}
}
var centers = dict.Where(x => x.Key != uf.Find(whiteID)).Select(x => new Tuple<double, double>(x.Value.Select(y => y.Item1).Average(), x.Value.Select(y => y.Item2).Average())).ToArray();
double min = int.MaxValue;
for (int i = 0; i < centers.Length - 1; i++)
{
for (int j = i + 1; j < centers.Length; j++)
{
var dist = Min(min, Sqrt(Pow(centers[i].Item1 - centers[j].Item1, 2) + Pow(centers[i].Item2 - centers[j].Item2, 2)));
min = Min(min, dist);
}
}
return min.ToString();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment