Pagini recente » Cod sursa (job #1204846) | Cod sursa (job #2291196) | Cod sursa (job #1762049) | Cod sursa (job #405524) | Cod sursa (job #2327856)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
double x, y;
};
punct p[120002], s[120002];
double pi(punct A, punct B, punct C)
{
return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
int criteriu (punct A, punct B)
{
return pi(A, B, p[0])>0;
}
int n, i, sf, poz;
double miny, minx;
int main()
{
fin >> n;
n--;
for(i=0;i<=n;i++)
{
fin >> p[i].x >> p[i].y;
if(p[i].y<miny)
{
miny=p[i].y;
minx=p[i].y;
poz=i;
}
else if(p[i].y==miny&&p[i].x<minx)
{
minx=p[i].x;
poz=i;
}
}
swap(p[0], p[poz]);
sort(p+1, p+n+1, criteriu);
s[0]=p[0];
s[1]=p[1];
s[2]=p[2];
sf=2;
for(i=3;i<=n;i++)
{
while(pi(p[i], s[sf], s[sf-1])>0)
sf--;
sf++;
s[sf]=p[i];
}
fout << sf+1 << '\n';
for(i=0;i<=sf;i++)
fout << setprecision(12) << fixed << p[i].x << ' ' << p[i].y << '\n';
return 0;
}