Pagini recente » Cod sursa (job #3353259) | Cod sursa (job #3340495) | Cod sursa (job #3325946) | Cod sursa (job #276985) | Cod sursa (job #3347719)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int nmax=120000;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,ss[nmax+1];
struct Point{
double x,y;
}p[nmax+1];
double det(Point a,Point b,Point c){
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
bool polar_sort(Point a,Point b){
return det(p[1],a,b)>0;
}
void read(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>p[i].x>>p[i].y;
}
void find_extreme(){
int mini=1;
for(int i=2;i<=n;i++)
if(p[i].y<p[mini].y || (p[i].y==p[mini].y && p[i].x<p[mini].x))
mini=i;
swap(p[1],p[mini]);
}
void graham_scan(){
for(int i=1;i<=n;i++){
while(ss[0]>=2 && det(p[ss[ss[0]-1]],p[ss[ss[0]]],p[i])<0)
ss[0]--;
ss[++ss[0]]=i;
}
}
void print_hull(){
fout<<ss[0]<<'\n';
for(int i=1;i<=ss[0];i++)
fout<<p[ss[i]].x<<' '<<p[ss[i]].y<<'\n';
}
int main() {
ios_base::sync_with_stdio (false);
cin.tie (nullptr);
read();
find_extreme();
sort(p+2,p+n+1,polar_sort);
graham_scan();
fout<<fixed<<setprecision(6);
print_hull();
//for(int i=1;i<=n;i++)
//cout<<p[i].x<<' '<<p[i].y<<'\n';
return 0;
}