Pagini recente » Cod sursa (job #2801703) | Cod sursa (job #2581849) | Cod sursa (job #1333384) | Cod sursa (job #130123) | Cod sursa (job #1607005)
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double,double> Point;
Point V[100005],stack[100005];
int head,n;
void read(){
f>>n;
for(int i=1;i<=n;i++){
f>>V[i].first>>V[i].second;
}
}
double cross_product(const Point& A,const Point& B,const Point& C){
return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
bool comp1(const Point& A,const Point& B){
return cross_product(V[1],A,B)<0;
}
void sort_points(){
int pos=1;
for(int i=2;i<=n;i++){
if(V[pos]>V[i]){
pos=i;
}
}
swap(V[1],V[pos]);
sort(V+2,V+n+1,comp1);
}
void convex(){
stack[1]=V[1];
stack[2]=V[2];
head=2;
for(int i=3;i<=n;i++){
while(head>=2 && cross_product(stack[head-1],stack[head],V[i])>0){
--head;
}
stack[++head]=V[i];
}
}
void solve(){
convex();g<<fixed<<head<<endl;
for(int i=head;i>=1;i--){
g<<setprecision(9)<<stack[i].first<<" "<<stack[i].second<<endl;
}
}
int main()
{
read();
sort_points();
solve();
return 0;
}