Pagini recente » Cod sursa (job #2337446) | Cod sursa (job #2914759) | Cod sursa (job #3153249) | Cod sursa (job #3191852) | Cod sursa (job #2052072)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coords{
double x,y;
};
const int NMAX=120000;
coords v[NMAX],s[NMAX];
int n,k;
void read_data(){
int i;
fin>>n;
for(i=1;i<=n;++i)
fin>>v[i].x>>v[i].y;
}
bool compare(const coords &P1,const coords &P2){
if(P1.x<P2.x)
return true;
if(P1.x==P2.x)
if(P1.y<P2.y)
return true;
return false;
}
int cross_product(const coords &P1,const coords &P2,const coords &P3){
return (P1.y-P3.y)*(P1.x-P2.x)-(P1.y-P2.y)*(P1.x-P3.x);
}
bool cmp(const coords &P1,const coords &P2){
return cross_product(v[1],P1,P2)<0;
}
void sort_data(){
int i,pos=1;
for(i=2;i<=n;++i)
if(compare(v[i],v[pos]))
pos=i;
swap(v[pos],v[1]);
sort(v+2,v+1+n,cmp);
}
void convex_hull(){
int i;
s[1]=v[1];
s[2]=v[2];
k=2;
for(i=3;i<=n;++i){
while(k>=2 and cross_product(s[k],s[k-1],v[i])<0)
--k;
s[++k]=v[i];
}
}
void print(){
int i;
for(i=k;i>=1;--i)
fout<<fixed<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
}
int main(){
read_data();
sort_data();
convex_hull();
print();
}