Pagini recente » Cod sursa (job #1274242) | Cod sursa (job #2552306) | Cod sursa (job #957541) | Cod sursa (job #2908522) | Cod sursa (job #1898598)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x,y;
}stk[121000],A[121000],sr;
int N,mpoz,hd;
void read(){
fin >>N;
for (int i=1;i<=N;i++) fin >>A[i].x>>A[i].y;
}
double cross(point a,point b,point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp(point a,point b){
return (cross(A[1],a,b))<0;
}
void arrange(){
sr=A[1];
mpoz=1;
for (int i=2;i<=N;i++){
if (A[i].x<sr.x || (A[i].x==sr.x && A[i].y<sr.y)){
sr=A[i];
mpoz=i;
}
}
swap(A[1],A[mpoz]);
sort(A+2,A+N+1,comp);
}
void solve(){
arrange();
stk[1]=A[1];
stk[2]=A[2];
hd=2;
for (int i=3;i<=N;i++){
while (hd>=2 && cross(stk[hd-1],stk[hd],A[i])>0) --hd;
stk[++hd]=A[i];
}
}
void afis(){
fout <<hd<<endl;
for (int i=hd;i>=1;i--) fout <<fixed<<setprecision(9)<<stk[i].x<<" "<<stk[i].y<<"\n";
}
int main(){
read();
solve();
afis();
return 0;
}