Pagini recente » Cod sursa (job #159285) | Cod sursa (job #3183691) | Cod sursa (job #1189512) | Cod sursa (job #467979) | Cod sursa (job #1609646)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <limits.h>
#include <stack>
#define MAX 1000000000
using namespace std;
struct Point
{
float x, y;
} O,v[120100],stiva[120100],prev;
int N,H,head;
bool compare(Point p1, Point p2)
{
float a = (p1.x - O.x) * (p2.y - O.y);
float b = (p2.x - O.x) * (p1.y - O.y);
return a >= b;
}
bool spre_dreapta(Point p0,Point p1, Point p2)
{
float u1,u2,v1,v2;
u1 = p1.x - p0.x;
u2 = p1.y - p0.y;
v1 = p2.x - p0.x;
v2 = p2.y - p0.y;
return (u1*v2 - u2*v1) < 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
O.x = MAX;
O.y = MAX;
int pos;
for(int i=1; i<=N; ++i)
{
scanf("%f%f",&v[i].x,&v[i].y);
if(O.x > v[i].x || O.x == v[i].x && O.y > v[i].y)
{
O = v[i];
pos = i;
}
}
swap(v[1], v[pos]);
sort(v+2,v+N+1,compare);
stiva[1]=v[1];
stiva[2]=v[2];
head = 2;
for(int i=3; i<=N; i++)
{
while(head>=2&&spre_dreapta(stiva[head-1],stiva[head],v[i]))
head--;
stiva[++head]= v[i];
}
printf("%d\n",head);
for(int i=1;i<=head;i++)
printf("%f %f\n",stiva[i].x,stiva[i].y);
return 0;
}