Pagini recente » Cod sursa (job #42846) | Cod sursa (job #2688362) | Cod sursa (job #1015658) | Cod sursa (job #1634630) | Cod sursa (job #3245519)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x,y;
int parte;
};
punct v[120003];
int stiva[120003];
bool cmp(punct a,punct b){
return (a.x < b.x);
return (a.y < b.y);
}
double arie(punct a,punct b,punct c){
return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
}
int main(){
int n,i,k;
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
for (i=2;i<n;i++){
if (arie(v[1],v[n],v[i]) < 0)
v[i].parte=1;
else
v[i].parte=2;
}
stiva[1]=1;
k=1;
for (i=2;i<=n;i++){
if (v[i].parte!=2){
while (k>1 && arie(v[stiva[k-1]],v[stiva[k]],v[i]) < 0)
k--;
k++;
stiva[k]=i;
}
}
int cop=k;
stiva[k]=n;
for (i=n-1;i>=1;i--){
if (v[i].parte!=1){
while (k > cop && arie(v[stiva[k-1]],v[stiva[k]],v[i]) < 0)
k--;
k++;
stiva[k]=i;
}
}
fout<<k-1<<'\n';
for (i=1;i<=k-1;i++)
fout<<fixed<<setprecision(6)<<v[stiva[i]].x<<' '<<v[stiva[i]].y<<'\n';
return 0;
}