Pagini recente » Cod sursa (job #1112725) | Istoria paginii runda/test_icrisop_2 | Cod sursa (job #1888838) | Cod sursa (job #464587) | Cod sursa (job #680444)
Cod sursa(job #680444)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("infasuratoare.in");
ofstream fo ("infasuratoare.out");
const int dim = 120005;
int N, I[dim], cadran2;
double X, Y;
struct pct { double x, y; } P[dim];
int cmp (pct a, pct b)
{
if (a.x * b.y == b.x * a.y)
{
if (a.x == 0 && b.x == 0)
return a.y > b.y;
if (cadran2)
return a.x > b.x;
else
return a.x < b.x;
}
return a.x * b.y > b.x * a.y;
}
double arie (double x1, double y1, double x2, double y2, double x3, double y3)
{
return (x3 - x2)*(y1 - y2)-(x1 - x2)*(y3 - y2);
}
void cit ()
{
int m = 0;
fi >> N;
for (int i = 0; i < N; i++)
{
fi >> P[i].x >> P[i].y;
if (P[i].y < P[m].y)
m = i;
}
X = P[m].x;
Y = P[m].y;
P[m] = P[0];
P[0].x = X;
P[0].y = Y;
}
void prep1 ()
{
for (int i = 0; i < N; i++)
{
P[i].x -= X;
P[i].y -= Y;
if (P[i].x < 0)
cadran2 = 1;
}
sort (P + 1, P + N, cmp);
}
void infc ()
{
I[0] = 2, I[1] = 0, I[2] = 1;
for (int i = 2; i < N; i++)
{
while (I[0] > 2 && arie (P[I[I[0]-1]].x, P[I[I[0]-1]].y, P[I[I[0]]].x, P[I[I[0]]].y, P[i].x, P[i].y) < 0)
I[0]--;
I[++I[0]] = i;
}
}
void prep2 ()
{
for (int i = 0; i < N; i++)
{
P[i].x += X;
P[i].y += Y;
}
}
void afi ()
{
fo << I[0] << '\n';
for (int i = 1; i <= I[0]; i++)
fo << P[I[i]].x << ' ' << P[I[i]].y << '\n';
}
int main ()
{
cit ();
prep1 ();
infc ();
prep2 ();
afi ();
return 0;
}