Pagini recente » Cod sursa (job #1081324) | Cod sursa (job #2598385) | Cod sursa (job #295889) | Cod sursa (job #2324821) | Cod sursa (job #2049281)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define lim 120010
struct point {double x, y;} ini[lim], stiva[lim];
int n,minm;
double det(point a, point b, point c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - c.y*a.x;
}
bool cmp (point A, point B)
{
return det (ini[1],A,B) >=0;
}
int main()
{
fin>>n;
minm=1;
for (int i=1; i<=n; i++)
{
fin>>ini[i].x>>ini[i].y;
if (ini[i].x > ini[minm].x) minm=i;
else if (ini[i].x==ini[minm].x && ini[i].y<ini[minm].y) minm=i;
}
swap (ini[1], ini[minm]);
sort (ini+2, ini+n+1, cmp);
int dr=0;
for (int i=1; i<=n; i++)
{
while (dr>1 && det (stiva[dr-1],stiva[dr],ini[i]) < 0) dr--;
dr++;
stiva[dr]=ini[i];
}
fout<<dr<<'\n';
for (int i=1; i<=dr; i++)
fout<<fixed<<stiva[i].x<<' '<<stiva[i].y<<'\n';
fin.close();
fout.close();
return 0;
}