Pagini recente » Cod sursa (job #236747) | Cod sursa (job #94877) | Cod sursa (job #1831839) | Cod sursa (job #2481237) | Cod sursa (job #2176028)
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct punct
{
double x,y;
bool trigorder(punct p1,punct p2)
{
double r=(p1.x*p2.y+x*p1.y+y*p2.x-p1.x*y-p2.x*p1.y-p2.y*x);
return (p1.x*p2.y+x*p1.y+y*p2.x-p1.x*y-p2.x*p1.y-p2.y*x)>0;
}
}vPuncte[120005];
int n;
void citire()
{
scanf("%d",&n);
int idx=1;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
if((vPuncte[i].x<vPuncte[idx].x)||(vPuncte[i].x==vPuncte[idx].x&&vPuncte[i].y<vPuncte[idx].y))
{
idx=i;
}
}
swap(vPuncte[1],vPuncte[idx]);
}
bool cmp(punct p1,punct p2)
{
return vPuncte[1].trigorder(p1,p2);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(vPuncte+2,vPuncte+n+1,cmp);
int stiva[120005],idx=2;
stiva[1]=1;
stiva[2]=2;
for(int i=3;i<=n;i++)
{
if(vPuncte[stiva[idx-1]].trigorder(vPuncte[stiva[idx]],vPuncte[i])||idx<2)
{
stiva[++idx]=i;
}
else
{
idx--;
i--;
}
}
printf("%d\n",idx);
for(int i=1;i<=idx;i++)
{
printf("%f %f\n",vPuncte[stiva[i]].x,vPuncte[stiva[i]].y);
}
return 0;
}