Pagini recente » Cod sursa (job #510525) | Cod sursa (job #2180688) | Cod sursa (job #3171251) | Cod sursa (job #321056) | Cod sursa (job #1650665)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120005
#define x first
#define y second
using namespace std;
ifstream g("infasuratoare.in");
ofstream f("infasuratoare.out");
typedef pair<double,double> Point;
int N,varf;
Point S[NMax],V[NMax];
void Citire()
{
g>>N;
for(int i=1;i<=N;i++)
g>>V[i].x>>V[i].y;
}
inline double ProdusIncrucisat(Point A,Point B,Point C)
{
return ((B.x-A.x)*(C.y-A.y))-((B.y-A.y)*(C.x-A.x));
}
inline int comp(Point p1,Point p2)
{
return ProdusIncrucisat(V[1],p1,p2)<0;
}
void Sortare()
{
int poz=1;
for(int i=2;i<=N;i++)
if(V[i]<V[poz])
poz=i;
swap(V[1],V[poz]);
sort(V+2,V+N+1,comp);
}
void InfasurareConvexa()
{
Sortare();
S[1]=V[1];
S[2]=V[2];
varf=2;
for(int i=3;i<=N;i++)
{
while(varf>=2 && ProdusIncrucisat(S[varf-1],S[varf],V[i])>0)
varf--;
S[++varf]=V[i];
}
}
void Afisare()
{
f<<fixed;
f<<varf<<"\n";
for(int i=varf;i>=1;i--)
f<<setprecision(9)<<S[i].x<<' '<<S[i].y<<"\n";
}
int main()
{
Citire();
InfasurareConvexa();
Afisare();
}