Pagini recente » Cod sursa (job #1103353) | Cod sursa (job #422468) | Cod sursa (job #2074519) | Cod sursa (job #1636993) | Cod sursa (job #2556976)
// 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));
return determinant;
}
void read()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf %lf", &P[i].x, &P[i].y);
}
void findP0()
{
int pozP0 = 1;
P0 = P[1];
for(int i = 2; i <= n; ++i)
if(P[i].y < P[pozP0].y || (P[i].y == P[pozP0].y && P[i].x < P[pozP0].x))
pozP0 = i;
swap(P[pozP0], P[1]);
P0 = P[1];
}
bool cmp(point B, point C)
{
return (orientation(P0, B, C) > 0);
}
void sortPoints()
{
findP0();
sort(P+2, P+n+1, cmp);
}
void infasuratoare()
{
S[1] = P0;
S[2] = P[2];
head = 2;
for(int i = 3; 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;
}