Pagini recente » Cod sursa (job #739314) | Cod sursa (job #1424641) | Cod sursa (job #2310618) | Cod sursa (job #1517477) | Cod sursa (job #1497069)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120001;
struct pnt{
double x,y;
pnt(){}pnt(double _x,double _y){x=_x,y=_y;}
} v[Nmax],s[Nmax];
double ccw(const pnt &A,const pnt &B,const pnt &C){
return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;
}
struct cmp1{
inline bool operator () (const pnt &A,const pnt &B){
if(A.x<B.x) return A.y<B.y;
return A.x<B.x;
}
};
struct cmp2{
inline bool operator () (const pnt &A,const pnt &B){
return ccw(v[1],A,B) > 0;
}
};
int N,K;
int main(){
in>>N;
double x,y;
for(int i=1;i<=N;i++){
in>>x>>y;
v[i]=pnt(x,y);
}
sort(v+1,v+N+1,cmp1());
sort(v+2,v+N+1,cmp2());
s[++K]=v[1],s[++K]=v[2];
for(int i=3;i<=N;i++){
while(K>1 && ccw(s[K-1],s[K],v[i])<0) K--;
s[++K]=v[i];
}
out<<K<<'\n';
out.precision(10);
for(int i=1;i<=K;i++){
out<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
}
return 0;
}