Pagini recente » Cod sursa (job #85647) | Cod sursa (job #700425) | Cod sursa (job #401357) | Cod sursa (job #2589044) | Cod sursa (job #1226597)
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const double eps=1.e-12;
class point{
private: double x,y;
public:
point(){
x=0;
y=0;
}
point(double xx,double yy){
x=xx;
y=yy;
}
double getx(){
return x;
}
double gety(){
return y;
}
bool ccw(const point &p2,const point &p3){
return (p2.x-x)*(p3.y-p2.y)-(p2.y-y)*(p3.x-p2.x)>=eps;
}
};
point v[120001];
int sol[120001];
bool cmp(point a,point b){
if(v[0].ccw(a,b)){
return 1;
}
return 0;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,top;
double x,y;
scanf("%d%lf%lf",&n,&x,&y);
point ll(x,y);
v[0]=ll;
for(int i=1;i<n;++i){
scanf("%lf%lf",&x,&y);
point aux(x,y);
v[i]=aux;
if(((fabs(y-v[0].gety())<eps)&&(x-v[0].gety()<=-eps))||(y-v[0].gety()<=-eps)){
swap(v[0],v[i]);
}
}
sort(v+1,v+n,cmp);
v[n]=v[0];
sol[0]=0;
sol[1]=1;
top=1;
int i=2;
while(i<=n){
if(v[sol[top-1]].ccw(v[sol[top]],v[i])){
sol[++top]=i;
++i;
}
else
--top;
}
printf("%d\n",top);
for(int i=0;i<top;++i){
printf("%lf %lf\n",v[sol[i]].getx(),v[sol[i]].gety());
}
return 0;
}