Pagini recente » Cod sursa (job #449433) | Cod sursa (job #1540327) | Cod sursa (job #3132550) | Cod sursa (job #117912) | Cod sursa (job #1337132)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define Nmax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int pozmin=0,head;
struct punct
{
double x,y;
};
punct p[Nmax],s[Nmax];
int n;
void read()
{
fin>>n;
int i;
p[0].y=10000000000;
p[0].x=10000000000;
for(i=1;i<=n;i++)
{
fin>>p[i].x;
fin>>p[i].y;
if(p[i].y<p[pozmin].y) pozmin=i;
else
if(p[i].y==p[pozmin].y)
if(p[i].x<p[pozmin].x) pozmin=i;
}
swap(p[pozmin],p[1]);
}
int determinant(double x1, double y1, double x2, double y2, double x3, double y3)
{
double det;
det=x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2;
return det;
}
int cmp(punct p1,punct p2)
{
return (determinant(p[1].x,p[1].y,p1.x,p1.y,p2.x,p2.y)) >0;
}
void solve()
{
s[1]=p[1];
s[2]=p[2];
head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && determinant(p[i].x,p[i].y, s[head].x,s[head].y, s[head-1].x,s[head-1].y) > 0)
head--;
s[++head]=p[i];
}
}
int main()
{
read();
sort(p+2,p+n+1, cmp);
solve();
fout<<head<<" \n";
while(head)
{
fout<<fixed<<setprecision(12)<<s[head].x<<" "<<s[head].y<<"\n";
head--;
}
return 0;
}