Pagini recente » Cod sursa (job #866407) | Cod sursa (job #255465) | Cod sursa (job #136243) | Cod sursa (job #2666850) | Cod sursa (job #1226776)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 120010
#define INF 2000000000
#define EPS 0.0000001
struct punct
{
double x,y,tan;
};
punct v[NMAX];
int n, num;
int st[NMAX];
inline bool egal0(const double &x)
{
return x+EPS>=0 && x-EPS<=0;
}
inline int ccw(const punct &a, const punct &b, const punct &c)
{
double x=(a.x-b.x)*(c.y-a.y)-(a.y-b.y)*(c.x-a.x);
if(egal0(x))
return 0;
return x>0 ? 1 : -1;
}
inline bool cmpP(const punct &a, const punct &b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
inline bool cmpT(const punct &a, const punct &b)
{
int x= ccw(v[0], a, b);
if(x==0)
return cmpP(a, b);
return x < 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int poz=0;
scanf("%d", &n);
for(int i=0; i<=n; ++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v, v+n, cmpP);
sort(v+1, v+n, cmpT);
v[n]=v[0];
while(poz<=n)
{
if(ccw(v[st[num-1]], v[st[num]], v[poz]) >= 0 && num >= 1)
{
--num;
}else
{
st[++num]=poz;
++poz;
}
}
printf("%d\n", num);
for(int i=0; i<num; ++i)
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}