Pagini recente » Cod sursa (job #2485203) | Cod sursa (job #1898847) | Cod sursa (job #1629213) | Cod sursa (job #1180292) | Cod sursa (job #2137318)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double EPS = 1e-12;
int N,H;
struct punct{
double x,y;
}p[120001],sol[120001];
double det(punct a,punct b,punct c)
{
//return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.x*c.y-a.y*b.x;
return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
int cmp(punct a, punct b)
{
if(abs(det(p[1],a,b))<EPS)
{
return abs(p[1].x-a.x)<abs(p[1].x-b.x);
}
if(det(p[1],a,b)<EPS) return 0;
return 1;
}
void inf_conv()
{
sort(p+2,p+N+1,cmp);
H=2;
sol[1]=p[1];
sol[2]=p[2];
for(int i=3; i<=N; i++)
{
while(H>=2 && det(sol[H-1],sol[H],p[i])<EPS) H--;
H++;
sol[H]=p[i];
}
}
int main()
{
f>>N;
f>>p[1].x>>p[1].y;
int j=1;
for(int i=2; i<=N; i++)
{f>>p[i].x>>p[i].y;
if(p[i].x<p[j].x) j=i;
else if(p[i].x==p[j].x && p[i].y<p[j].y) j=i;
}
swap(p[1],p[j]);
inf_conv();
g<<H<<'\n';
g<<fixed<<setprecision(6);
for(int i=1;i<=H;i++)
{
g<<sol[i].x<<' '<<sol[i].y<<'\n';
}
return 0;
}