Pagini recente » Cod sursa (job #2569042) | Cod sursa (job #521128) | Cod sursa (job #2065042) | Cod sursa (job #2177551) | Cod sursa (job #1095800)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 120005
struct Point
{
double x,y;
};
Point V[NMAX];
Point Queue[NMAX];
int N;
int QVaf;
void Read()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%lf%lf",&V[i].x,&V[i].y);
}
double determinant(Point a, Point b, Point c)
{
return a.x*b.y + a.y*c.x + b.x*c.y - b.y*c.x - a.y*b.x - a.x*c.y;
}
bool cmp(Point i, Point j)
{
return determinant(V[1],i,j) > 0;
}
void Solve()
{
int MinI = 1;
for(int i=2;i<=N;i++)
if(V[i].y < V[MinI].y || (V[i].y == V[MinI].y && V[i].x < V[MinI].x))
MinI = i;
swap(V[1], V[MinI]);
sort(V+2,V+N+1,cmp);
Queue[1] = V[1];
Queue[2] = V[2];
QVaf = 2;
for(int i=3;i<=N;i++)
{
while(QVaf>=1 && determinant(Queue[QVaf-1],Queue[QVaf],V[i]) < 0)
QVaf--;
Queue[++QVaf] = V[i];
}
}
void Print()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",QVaf);
for(int i=1;i<=QVaf;i++)
printf("%.6lf %.6lf\n",Queue[i].x,Queue[i].y);
}
int main()
{
Read();
Solve();
Print();
return 0;
}