Pagini recente » Cod sursa (job #447288) | Cod sursa (job #1600780) | Cod sursa (job #339082) | Cod sursa (job #752190) | Cod sursa (job #1094882)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define INF 4611686018427387904
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct QQ{
long double x;
long double y;
long double p;
}a[120005];
bool cmp(QQ i, QQ j ){
if(i.p == j.p){
return i.y > j.y;
}
else
return i.p < j.p;
}
int stiva[120005];
int main(){
int n,i;
long double x0=1000000005,y0=1000000005;
f>>n;
for(i=1; i<=n; ++i){
f>>a[i].x>>a[i].y;
if(a[i].x == x0){
if(a[i].y < y0){
x0=a[i].x;
y0=a[i].y;
}
}
else
if(a[i].x < x0){
x0=a[i].x;
y0=a[i].y;
}
}
for(i=1; i<=n; ++i){
if(a[i].x - x0 == 0){
a[i].p=INF;
}
else{
a[i].p=(a[i].y - y0)/(a[i].x - x0);
}
}
sort(a+1, a+n+1, cmp);
a[0].x=x0;
a[0].y=y0;
stiva[0]=0;
stiva[1]=1;
stiva[2]=2;
int st1 = 2;
long double m;
for(i=3; i<n; ++i){
do{
m=(a[stiva[st1]].y - a[stiva[st1-1]].y )*(a[i].x -a[stiva[st1]].x) - (a[i].y - a[stiva[st1]].y)*(a[stiva[st1]].x - a[stiva[st1-1]].x);
if(m>0)
st1--;
}while(m>0);
stiva[++st1]=i;
}
g<<fixed;
g<<st1+1<<'\n';
for(i=0; i<=st1; ++i){
g.precision(6);
g<<a[stiva[i]].x<<' '<<a[stiva[i]].y<<'\n';
}
return 0;
}