Pagini recente » Cod sursa (job #261852) | Cod sursa (job #1137860) | Cod sursa (job #1297172) | Cod sursa (job #2712693) | Cod sursa (job #1254726)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
struct punct{
double x;
double y;
};
const int MAX_N = 120005;
int st[MAX_N],k;
bool viz[MAX_N];
punct a[MAX_N];
int i,n,p;
short int semn(const punct &A, const punct &B, const punct &P){
double x = (B.x*P.y + A.x*B.y + A.y*P.x - B.x*A.y - P.x*B.y - P.y*A.x);
if(x>0) return 1;
if(x<0) return (-1);
return 0;
}
bool comp(const punct &a, const punct &b){
if(a.x==b.x) return (a.y<b.y);
else return (a.x<b.x);
}
int main(){
fi>>n;
for(i=1;i<=n;i++) fi>>a[i].x>>a[i].y;
sort(a+1,a+n+1,comp);
st[1]=1; st[2]=2; k=2;
viz[1]=0; viz[2]=1;
for(i=3,p=1; i>0; i+=(p=(i==n)?(-p):(p)))
if(!viz[i]){
while(k>=2 && semn(a[st[k-1]],a[st[k]],a[i])<=0) viz[st[k--]]=0;
st[++k]=i;
viz[i]=1;
}
k--;
fo<<k<<'\n';
for(i=1;i<=k;i++)
fo<<fixed<<setprecision(8)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
fi.close();
fo.close();
return 0;
}