Pagini recente » Cod sursa (job #2092069) | Cod sursa (job #2254445) | Cod sursa (job #3265189) | Cod sursa (job #2484991) | Cod sursa (job #239596)
Cod sursa(job #239596)
# include <cstdio>
# include <math.h>
# include <cmath>
# include <algorithm>
using namespace std;
# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define min(a, b) (a < b ? a : b)
# define max(a, b) (a > b ? a : b)
# define sqr(a) (a * a)
# define MAXN 120005
struct trio
{
double x, y, U;
} Pct[MAXN];
int N, jos;
int S[MAXN];
double phi = 4 * atan(1), MaxU, MinU = 180.0, x, y;
double dist(trio A, trio B)
{
return sqrt(sqr((A.x-B.x))+sqr((A.y-B.y)));
}
int cmp(trio A, trio B)
{
if (A.U != B.U) return A.U < B.U;
return dist(A, Pct[jos]) < dist(B, Pct[jos]);
}
void compute(int i)
{
double rap;
if (Pct[i].x == Pct[jos].x)
{
Pct[i].U = 90.0;
return;
}
rap = abs((Pct[i].y-Pct[jos].y)/(Pct[i].x-Pct[jos].x));
Pct[i].U = atan(rap) * 180 / phi;
if (Pct[i].x < Pct[jos].x) Pct[i].U = 180.0 - Pct[i].U;
MinU = min(MinU, Pct[i].U);
MaxU = max(MaxU, Pct[i].U);
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&N);
for (int i = jos = 1; i <= N; ++i)
{
scanf("%lf %lf",&Pct[i].x, &Pct[i].y);
if (Pct[i].y < Pct[jos].y) jos = i;
}
for (int i = 1; i <= N; ++i)
if (i != jos) compute(i);
sort(Pct + 1, Pct + N + 1, cmp);
int ct = 1, i, ok;
S[1] = 1;
for (i = 2; Pct[i].U == MinU; ++i)
S[++ct] = i;
for (; Pct[i-1].U != MaxU; ++i)
{
ok = 1;
while (ok)
{
x = (Pct[S[ct-1]].x-Pct[i].x)*(Pct[S[ct]].y-Pct[i].y);
y = (Pct[S[ct]].x-Pct[i].x)*(Pct[S[ct-1]].y-Pct[i].y);
if (x - y < 0) --ct;
else
{
++ct;
ok = 0;
}
}
S[ct] = i;
}
for (int j = N; j >= i; --j)
S[++ct] = j;
printf("%d\n",ct);
for (int i = 1; i <= ct; ++i)
printf("%lf %lf\n",Pct[S[i]].x, Pct[S[i]].y);
return 0;
}