Pagini recente » Cod sursa (job #1505375) | Cod sursa (job #3252390) | Cod sursa (job #1560658) | Cod sursa (job #1627282) | Cod sursa (job #1226617)
#include <cstdio>
#include <algorithm>
#include <cmath>
// GRAHAM SCAN O(nlogn)
using namespace std;
const double eps=1.e-12;
const int LIMIT=120005;
struct POINT
{
double x,y;
}P[LIMIT];
inline bool ccw(const POINT &a, const POINT &b, const POINT &c)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x)>0;
}
inline bool cmp(const POINT &a, const POINT &b)
{
return ccw(P[0],a,b);
}
int st[LIMIT];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,top;
scanf("%d %lf %lf",&n,&P[0].x,&P[0].y); // P[0] = low left
for(i=1;i<n;++i)
{
scanf("%lf %lf",&P[i].x,&P[i].y);
if((fabs(P[i].y-P[0].y)<eps && P[i].x-P[0].x<=-eps) || P[i].y-P[0].y<=-eps)
swap(P[0],P[i]);
}
sort(P+1,P+n,cmp);
P[n]=P[0];
st[0]=0;
st[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(P[st[top-1]],P[st[top]],P[i]))
st[++top]=i++;
else
--top;
}
printf("%d\n",top);
for(i=0;i<top;++i)
printf("%6lf %6lf\n",P[st[i]].x,P[st[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}