Pagini recente » Cod sursa (job #3164260) | Cod sursa (job #3237618) | Cod sursa (job #1384521) | Cod sursa (job #1616793) | Cod sursa (job #1002705)
#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;
} v[120010], p, aux, st[120010];
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);
}
bool cmp(puncte a, puncte b){
if(afla(v[1], a, b)>0)
return 1;
return 0;
}
int main(){
f>>n;
p.y=p.x=1000000010;
for(i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
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);
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;
}