Pagini recente » Cod sursa (job #3244541) | Cod sursa (job #299036) | Cod sursa (job #1217621) | Cod sursa (job #1111684) | Cod sursa (job #3216162)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
double x;
double y;
}point[120005];
punct poligon[120005];
int lgPoligon;
bool cmp(punct a,punct b)
{
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
if(a.x==b.x)
{
return (a.y<=b.y);
}
}
int orientare(punct a,punct b,punct c)
{
double det=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(det>0)
return 1;
if(det<0)
return 2;
if(det==0)
return 3;
}
void poligonSus()
{
for(int i=0;i<n;i++)
{
while(lgPoligon>=2 && orientare(poligon[lgPoligon-2],poligon[lgPoligon-1],point[i])!=1)
{
lgPoligon--;
}
poligon[lgPoligon++]=point[i];
}
}
void poligonJos()
{
for(int i=n-3;i>=0;i--)
{
while(lgPoligon>=2 && orientare(poligon[lgPoligon-2],poligon[lgPoligon-1],point[i])!=1)
{
lgPoligon--;
}
poligon[lgPoligon++]=point[i];
}
}
void citire()
{
fout<<fixed<<setprecision(6);
fin>>n;
for(int i=0;i<n;i++)
{
fin>>point[i].x;
fin>>point[i].y;
}
sort(point,point+n,cmp);
poligonSus();
poligon[lgPoligon++]=point[n-2];
poligonJos();
lgPoligon--;
fout<<lgPoligon<<'\n';
for(int i=0;i<lgPoligon;i++)
fout<<poligon[i].x<<" "<<poligon[i].y<<"\n";
}
int main()
{
citire();
return 0;
}