Pagini recente » Cod sursa (job #3285663) | Cod sursa (job #1272966) | Cod sursa (job #1713006) | Cod sursa (job #22875) | Cod sursa (job #3300596)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
long double x,y;
};
Punct pivot;
long double distanta(Punct a,Punct b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int orientare(Punct p,Punct q,Punct r)
{
long double val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
if(abs(val)<1e-12) return 0;
return (val>0) ? 1 : 2;
}
bool compara(Punct a, Punct b)
{
int o=orientare(pivot, a, b);
if(o==0) return distanta(pivot,a)<distanta(pivot,b);
return o==1;
}
int main()
{
int n;
fin>>n;
Punct puncte[120001];
int minim=0;
for(int i=0;i<n;i++)
{
fin>>puncte[i].x>>puncte[i].y;
if(puncte[i].y<puncte[minim].y || (puncte[i].y==puncte[minim].y && puncte[i].x<puncte[minim].x))
{
minim = i;
}
}
swap(puncte[0],puncte[minim]);
pivot=puncte[0];
sort(puncte+1,puncte+n,compara);
Punct infasuratoare[120001];
int dimensiune=0;
infasuratoare[dimensiune++]=puncte[0];
infasuratoare[dimensiune++]=puncte[1];
for(int i=2;i<n;i++)
{
while(dimensiune>=2 && orientare(infasuratoare[dimensiune-2],infasuratoare[dimensiune-1], puncte[i])!=1)
{
dimensiune--;
}
infasuratoare[dimensiune++]=puncte[i];
}
fout<<dimensiune<<endl;
fout<<fixed<<setprecision(6);
for(int i=0;i<dimensiune;i++)
{
fout<<infasuratoare[i].x<<" "<<infasuratoare[i].y<<endl;
}
fin.close();
fout.close();
return 0;
}