Pagini recente » Cod sursa (job #2110333) | Cod sursa (job #2710949) | Cod sursa (job #2617281) | Cod sursa (job #3282595) | Cod sursa (job #624239)
Cod sursa(job #624239)
#include<cstdio>
#include<algorithm>
#define infinit (1<<29)
using namespace std;
struct Punct { double x, y, panta; };
long n;
Punct L[120001], P[120001], punctStart;
inline double Determinant(Punct A, Punct B, Punct C)
{ return (A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - B.x * A.y); }
inline bool cmp(Punct A, Punct B)
{ return (A.panta < B.panta); }
inline double Distanta(Punct A, Punct B)
{ return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); }
void Citire()
{
long i;
punctStart = (Punct){-1000000001, -1000000001};
freopen("infasuratoare.in", "r", stdin);
scanf("%ld", &n);
for(i = 1; i <= n; i++)
{
scanf("%lf %lf", &L[i].x, &L[i].y);
if(L[i].x > punctStart.x) punctStart = L[i];
else if(L[i].x == punctStart.x && L[i].y < punctStart.y) punctStart = L[i];
}
fclose(stdin);
}
void Calcul()
{
long i, m = 0, top = 1;
P[++m] = punctStart;
for(i = 1; i <= n; i++)
if(L[i].x != punctStart.x || L[i].y != punctStart.y)
{
L[i].panta = punctStart.x == L[i].x ? -infinit : (punctStart.y - L[i].y) / (punctStart.x - L[i].x);
P[++m] = L[i]; // adaug punctele pentru sortare
}
sort(P + 2, P + m + 1, cmp); // sortez punctele in functie de panta
n = 1;
L[1] = P[1];
for(i = 2; i <= m; i++)
if(L[n].panta != P[i].panta) L[++n] = P[i];
else if(Distanta(L[1], L[n]) < Distanta(L[1], P[i])) L[n] = P[i];
for(i = 1; i <= n; i++)
{
while(top > 2 && Determinant(P[top - 2], P[top - 1], L[i]) < 0) top--;
P[top++] = L[i];
}
top--;
n = top;
}
int main()
{
long i;
Citire();
Calcul();
freopen("infasuratoare.out", "w", stdout);
printf("%ld\n", n);
for(i = 1; i <= n; i++) printf("%.6lf %.6lf\n", P[i].x, P[i].y);
fclose(stdout);
return 0;
}