Pagini recente » Cod sursa (job #1317120) | Cod sursa (job #1530150) | Cod sursa (job #1888073) | Cod sursa (job #1901841) | Cod sursa (job #2556960)
// fara puncte coliniare!
#define NMAX 120005
#include <cstdio>
#include <algorithm>
using namespace std;
struct point{
double x, y;
bool operator>(const point &other) const {
}
}P[NMAX], P0;
int n;
point S[NMAX];
int head;
int orientation(point A, point B, point C)
{
double determinant = ((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
if(determinant < 0)
return -1;
if(determinant > 0)
return 1;
return 0;
}
void read()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf %lf", &P[i].x, &P[i].y);
}
void findP0()
{
P0 = P[1];
for(int i = 2; i <= n; ++i)
if(P[i].y < P0.y || (P[i].y == P0.y && P[i].x < P0.x))
P0 = P[i];
}
void delP0()
{
int i = 1;
while(P[i].x != P0.x && P[i].y != P0.y)
++i;
for(i; i <= n; ++i)
P[i] = P[i+1];
n--;
}
void sortPoints()
{
findP0();
delP0();
for(int i=1; i<n; ++i)
for(int j = i+1; j <= n; ++j)
if(orientation(P0, P[i], P[j]) < 0)
swap(P[j], P[i]);
}
void infasuratoare()
{
S[1] = P0;
S[2] = P[1];
head = 2;
for(int i = 2; i <= n; ++i)
{
while(head >= 2 && orientation(S[head-1], S[head], P[i]) < 0)
--head;
S[++head] = P[i];
}
}
void afis()
{
printf("%d\n", head);
for(int i = 1; i <= head; ++i)
printf("%.9f %.9f\n", S[i].x, S[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
sortPoints();
infasuratoare();
afis();
return 0;
}