Pagini recente » Cod sursa (job #2587947) | Cod sursa (job #1727938) | Cod sursa (job #1895997) | Cod sursa (job #451979) | Cod sursa (job #624236)
Cod sursa(job #624236)
#include<cstdio>
#include<algorithm>
#define infinit (1<<29)
using namespace std;
struct Punct { double x, y, panta; };
int n;
Punct L[201], P[201], 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()
{
int i;
punctStart = (Punct){-1000000001, -1000000001};
freopen("infasuratoare.in", "r", stdin);
scanf("%d", &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()
{
int i, m = 0;
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++) P[i] = (Punct){0, 0, 0};
int top = 1;
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()
{
int i;
Citire(); // citire
Calcul();
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", n);
for(i = 1; i <= n; i++) printf("%.6lf %.6lf\n", P[i].x, P[i].y);
fclose(stdout);
return 0;
}