Pagini recente » Cod sursa (job #2577529) | Istoria paginii runda/luca_oji | Cod sursa (job #1256658) | Cod sursa (job #1893273)
#include<fstream>
#include <algorithm>
#include <iomanip>
#define Lmax 120003
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct{
double x,y;
};
Punct a[Lmax],stiva[Lmax];
int n,i,k;
bool cmp(Punct a, Punct b)
{
if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
return false;
}
int det(Punct a,Punct b, Punct c){
if((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y)>=0)return 1;
else return 0;
}
int main()
{
fin>>n;
for(i = 1; i <= n; i++) fin>>a[i].x>>a[i].y;
sort(a + 1, a + n + 1, cmp);
stiva[1]=a[1];
k = 1;
for(i = 2; i <= n; i++)
{
while(k > 1 && !det(stiva[k-1], stiva[k], a[i])) k--;
stiva[++k]=a[i];
}
for(i = n - 1; i >= 1; i--)
{
while(!det(stiva[k-1], stiva[k], a[i]))k--;
stiva[++k]=a[i];
}
fout<<fixed<<setprecision(6);
fout<<k-1<<'\n';
for(i = 1; i <= k-1 ; i++) fout<< stiva[i].x <<" "<<stiva[i].y<<'\n';
fin.close();
fout.close();
return 0;
}