Pagini recente » Cod sursa (job #2969198) | Cod sursa (job #2182174) | Cod sursa (job #2110566) | Cod sursa (job #1854653) | Cod sursa (job #2476189)
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct data{
float x;
float y;
}v[120005],minim ;
vector <data> w;
bool minimul(data a, data b)
{
if(a.y==b.y)
return a.x < b.x ;
return a.y < b.y;
}
bool operator != (data a, data b)
{
if(a.x==b.x&&a.y==b.y)
return false;
return true;
}
float latura(data a, data b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
float unghi(float a, float b ,float c)
{
return acos( (b*b + c*c - a*a) / (2*b*c) );
}
data unghiul_bun(int n,data a ,data b )
{
data c,c_max;
float max_unghi=0,unghi1;
for(int i=1;i<=n;i++)
{
c=v[i];
unghi1 = unghi(latura(b,c) , latura(a,b) , latura(a,c) );
if(max_unghi < unghi1)
{
max_unghi=unghi1;
c_max=c;
}
}
return c_max;
}
int main()
{
int n,h=0,i;
data a,b,c;
fin>>n;
minim.x=1000000000;
minim.y=1000000000;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(minimul(v[i],minim))
minim=v[i];
}
b=minim;
a=minim;
a.x++;
c=unghiul_bun(n,b,a);
h++;
w.push_back(minim);
while(c!=minim)
{
h++;
w.push_back(c);
a=b;
b=c;
c=unghiul_bun(n,b,a);
}
fout<<h<<"\n";
for(i=0;i<w.size();i++)
{
fout<<w[i].x<<" "<<w[i].y<<"\n";
}
return 0;
}