Pagini recente » Cod sursa (job #2431269) | Cod sursa (job #2254278) | Cod sursa (job #2073654) | Cod sursa (job #1001305) | Cod sursa (job #2019677)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define pb(x) push_back(x)
#define x first
#define y second
using namespace std;
const int nmax=120005;
const double inf=2e9;
const double eps=1e-12;
typedef pair<double,double> dd;
dd punct[nmax];
int n,top;
inline double dist(dd p1,dd p2)
{
return sqrt((p1.x - p2.x)*(p1.x-p2.x) + (p1.y - p2.y)*(p1.y-p2.y));
}
inline double cp(dd p1,dd p2,dd p3)
{
return (p2.x-p1.x)*(p3.y-p2.y) - (p2.y-p1.y)*(p3.x-p2.x);
}
inline int ccw(dd p1,dd p2,dd p3)
{
double a=cp(p1,p2,p3);
if(a >= eps)
return 1;
if(a <= -eps)
return -1;
return 0;
}
inline bool cmp(const dd &p1, const dd &p2)
{
double c1=ccw(punct[1],p1,p2);
if(c1 == 1)
return 1;
if(c1 == 0)
return dist(punct[0],p1) - dist(punct[0],p2) < eps;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,j;
int ll=1;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%lf %lf",&punct[i].x,&punct[i].y);
if(punct[i].y -punct[ll].y <=-eps || (fabs(punct[i].y - punct[ll].y) < eps && punct[i].x - punct[ll].x <= -eps))
ll=i;
}
double aux=punct[1].x;
punct[1].x = punct[ll].x;
punct[ll].x = aux;
aux=punct[1].y;
punct[1].y = punct[ll].y;
punct[ll].y = aux;
sort(punct+2,punct+n+1,cmp);
vector<int> st(n+5);
st[0] = 1;
st[1] = 2;
punct[n+1]=punct[1];
top=1;
i=3;
while(i<=n+1)
{
if(ccw(punct[st[top-1]] , punct[st[top]] , punct[i]) > 0)
{
st[++top]=i;
++i;
}
else
--top;
}
printf("%d\n",(top));
for(i=0;i<top;++i)
{
printf("%lf %lf\n",punct[st[i]].x,punct[st[i]].y);
}
}