Pagini recente » Cod sursa (job #2310938) | Cod sursa (job #1631380) | Cod sursa (job #2563754) | Cod sursa (job #689870) | Cod sursa (job #834483)
Cod sursa(job #834483)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iostream>
#define Nmax 100010
#define INFI 0x3f3f3f3f
using namespace std;
int n, st[Nmax], viz[Nmax], k;
struct punct {
int x;
int y;
} p[Nmax];
int cmp (punct a, punct b)
{
if (a.x > b.x)
return 0;
if (a.x == b.x && a.y > b.y)
return 0;
return 1;
}
float det (punct a, punct b, punct c)
{
return (b.x * c.y + c.x * a.y + a.x * b.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}
int semn (punct a, punct b, punct c)
{
float d;
d = det (a, b, c);
if (d > 0)
return 1;
else
if (d < 0)
return -1;
else
return 0;
}
void convex ()
{
int i;
st[0] = 0;
st[1] = 1;
st[2] = 2;
viz[1] = viz[2] = 1;
k = 2;
i = 3;
int s = semn (p[st[0]], p[st[1]], p[st[2]]);
if (s == 0)
s = 1;
while (i < n)
{
float s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
while (s != s1 && s1 != 0)
{
viz[st[k]] = 0;
--k;
s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
}
++k;
st[k] = i;
viz[i] = 1;
++i;
}
--i;
while (st[k] != 0)
{
while (viz[i])
i--;
float s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
while (s != s1 && s1 != 0)
{
--k;
s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
}
++k;
st[k] = i;
--i;
}
}
float dist (int i, int j)
{
return sqrt(double(((p[i].x - p[j].x) * (p[i].x - p[j].x)) + ((p[i].y - p[j].y) * (p[i].y - p[j].y))));
}
float proiectie (int i, int j, int k)
{
float ar = det (p[i], p[j], p[k]);
ar = abs(ar);
return ar / dist (i, j);
}
float amax (int i1, int i2)
{
float maxh = -1;
float d1, d2;
float max1 = 0;
float max2 = 0;
float da = dist (i1, i2);
for (int i = 0; i < k; ++i)
{
if (st[i] != i1 && st[i] != i2)
{
float pr = proiectie (i1, i2, st[i]);
if (pr > maxh)
maxh = pr;
d1 = dist (i1, st[i]);
d2 = dist (i2, st[i]);
d1 = sqrt (double (d1 * d1 - pr * pr));
d2 = sqrt (double (d2 * d2 - pr * pr));
if (d1 > da && d2 > max2)
max2 = d2;
else
if (d2 > da && d1 > max1)
max1 = d1;
}
}
return maxh * (max2 + max1 + da);
}
int main()
{
ifstream f("rubarba.in");
ofstream h("rubarba.out");
f >> n;
for (int i = 0; i < n; ++i)
{
f >> p[i].x >> p[i].y;
}
f.close();
sort(p, p + n, cmp);
convex ();
float minim = INFI;
for (int i = 0; i < k; ++i)
{
float blabla = amax (st[i], st[i + 1]);
if (blabla < minim)
minim = blabla;
// cout << blabla << '\n';
}
//for (int i = 0; i < k; ++i)
//h << st[i] << " ";
minim = (int (minim * 100));
minim = minim / 100;
h << minim << '\n';
h.close();
return 0;
}