Pagini recente » Cod sursa (job #2835961) | Cod sursa (job #646325) | Cod sursa (job #595464) | Cod sursa (job #448351) | Cod sursa (job #1595352)
#include<fstream>
#include<iomanip>
#include<algorithm>
#define inf 1<<30
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,k,poz,i,fin[120005];
struct punct
{
double x,y,panta;
}a[120005],aux,min1;
int cmp(punct nr1,punct nr2)
{
if(nr1.panta==nr2.panta)
return nr1.x<nr2.x;
return nr1.panta<nr2.panta;
}
int conex()
{
punct nr1,nr2,nr3;
double arie;
nr1=a[fin[k-1]];
nr2=a[fin[k]];
nr3=a[i];
arie=(nr1.x*nr2.y+nr2.x*nr3.y+nr1.y*nr3.x-nr3.x*nr2.y-nr3.y*nr1.x-nr1.y*nr2.x)/2;
if(arie>0)
return 1;
return 0;
}
int main()
{
f>>n;
min1.x=inf;
min1.y=inf;
for(i=1;i<=n;i++)
{
f>>a[i].x>>a[i].y;
if(a[i].x<min1.x||a[i].x==min1.x&&a[i].y<min1.y)
{
min1=a[i];
poz=i;
}
}
aux=a[1];
a[1]=min1;
a[poz]=aux;
for(i=2;i<=n;i++)
a[i].panta=(a[i].y-a[1].y)/(a[i].x-a[1].x);
sort(a+2,a+n+1,cmp);
k=2;
fin[2]=2;
fin[1]=1;
for(i=3;i<=n;i++)
{
while(conex()==1&&k>2)
k--;
k++;
fin[k]=i;
}
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<fixed<<setprecision(6)<<a[fin[i]].x<<" "<<fixed<<setprecision(6)<<a[fin[i]].y<<"\n";
return 0;
}