Pagini recente » Cod sursa (job #1038912) | Cod sursa (job #107013) | Cod sursa (job #2883947) | Cod sursa (job #418474) | Cod sursa (job #2659682)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct{
double x,y;
} ;
punct v1[120001],v2[120001];
void citire(int &n,punct a[120001])
{
int i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].x;
fin>>a[i].y;
}
}
double determinant(punct a,punct b, punct c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-a.x*c.y-c.x*b.y-b.x*a.y;
}
bool cnd(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
};
void ordonare(int n,punct a[120001])
{
sort(a,a+n,cnd);
}
void formarev1(punct a[120001],int n,int &last)
{
v1[1]=a[1];
v1[2]=a[2];
last=2;
for(int i=3;i<=n;i++)
{
if(determinant(v1[last-1],v1[last],a[i])<0)
{
last--;
while(last!=1 && determinant(v1[last-1],v1[last],a[i])<0)
last--;
v1[++last]=a[i];
}
else if(determinant(v1[last-1],v1[last],a[i])>=0)
{
v1[++last]=a[i];
}
}
}
void formarev2(punct a[120001],int n,int &last)
{
v2[1]=a[1];
v2[2]=a[2];
last=2;
for(int i=3;i<=n;i++)
{
if(determinant(v2[last-1],v2[last],a[i])>0)
{
last--;
while(last!=1 && determinant(v2[last-1],v2[last],a[i])>0)
last--;
v2[++last]=a[i];
}
else if(determinant(v2[last-1],v2[last],a[i])<=0)
{
v2[++last]=a[i];
}
}
}
void afisare(int x,int y)
{
int i;
fout<<x+y-2<<"\n";
for(i=1;i<=x;i++)
fout<<fixed<<setprecision(6)<<v1[i].x<<" "<<v1[i].y<<"\n";
for(i=y-1;i>1;i--)
fout<<fixed<<setprecision(6)<<v2[i].x<<" "<<v2[i].y<<"\n";
}
int main()
{
int n,x,y;
punct a[120001];
citire(n,a);
ordonare(n,a);
formarev1(a,n,x);
formarev2(a,n,y);
afisare(x,y);
return 0;
}