Pagini recente » Cod sursa (job #1185483) | Cod sursa (job #1718167) | Cod sursa (job #2167084) | Cod sursa (job #142890) | Cod sursa (job #1002684)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i, ind, k;
struct puncte{
double x, y, r;
} v[120010], p, aux, st[120010];
bool cmp(puncte a, puncte b){
return a.r<b.r;
}
double afla(puncte a, puncte b, puncte c){
return (a.x*b.y+b.x*c.y+c.x*a.y)-(c.x*b.y+c.y*a.x+b.x*a.y);
}
int main(){
f>>n;
p.y=p.x=1000000010;
for(i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
v[i].r=v[i].y/v[i].x;
if(v[i].x<p.x || (v[i].x==p.x && v[i].y<p.y) )
{
p=v[i];
ind=i;
}
}
aux=v[1];
v[1]=v[ind];
v[ind]=aux;
sort(v+2, v+n+1, cmp);
/*for(i=1; i<=n; i++)
g<<v[i].x<<' '<<v[i].y<<"\n";*/
st[++k]=v[1];
st[++k]=v[2];
for(i=3; i<=n; i++)
{
while(k>=2 && afla(st[k-1], st[k], v[i])<0)
k--;
st[++k]=v[i];
}
g<<k<<"\n"<<fixed;
for(i=1; i<=k; i++)
g<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}