Pagini recente » Cod sursa (job #1156800) | Cod sursa (job #2234317) | Cod sursa (job #1759478) | Cod sursa (job #1898229) | Cod sursa (job #1039673)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<fstream>
using namespace std;
typedef struct punct
{
double x;
double y;
}pct;
pct v[120000];
int st[120000];
double unghi(pct A, pct B, pct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int cmp(pct vi, pct vj)
{
return (unghi(v[0], vi, vj)<0);
}
int main()
{
FILE *fin, *fout;
fin = fopen("infasuratoare.in", "r");
ofstream g("infasuratoare.out");
int n, i, prim, ultim;
fscanf(fin, "%d", &n);
for(i=0; i<n; i++)
fscanf(fin, "%lf %lf", &v[i].x, &v[i].y);
int min=0, auxx;
for(i=1; i<n; i++)
if(v[i].x<v[min].x)
min=i;
else
if(v[i].x==v[min].x)
if(v[i].y<v[min].y)
min=i;
auxx=v[0].x;
v[0].x=v[min].x;
v[min].x=auxx;
auxx=v[0].y;
v[0].y=v[min].y;
v[min].y=auxx;
sort(v+1, v+n, cmp);
st[0]=0;
st[1]=1;
prim=0; ultim=1;
for(i = 2; i<n; i++)
{
while(unghi( v[st[ultim-1]], v[st[ultim]], v[i]) > 0 && ultim>=1)
{ ultim--; }
ultim++;
st[ultim]=i;
}
g<<ultim-prim+1<<"\n";
for(i=ultim; i>=prim; i--)
{
g<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
}