Pagini recente » Cod sursa (job #322804) | Cod sursa (job #2153067) | Cod sursa (job #983204) | Cod sursa (job #1310187) | Cod sursa (job #2974578)
#include<fstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<algorithm>
#define dim 120005
using namespace std;
ifstream in("infasuratoareconvexa.in");
ofstream out("infasuratoareconvexa.out");
vector<int>v;
double x[dim],y[dim];
bool use[dim],ok;
int n,h;
void citire()
{
in>>n;
for(int i=1; i<=n; i++)
in>>x[i]>>y[i];
}
int main()
{
citire();
int mic=1,c,poz;
double unghi,minU,uAnt;
for(int i=2; i<=n; i++)
if(x[i]<x[mic])
mic=i;
c=mic;
ok=1;
uAnt=0;
while(ok==1 || c!=mic)
{
ok=0;
v.push_back(c);
poz=c;
minU=10000;
for(int i=1; i<=n; i++)
{
if(use[i]==1 || i==c)
continue;
unghi=atan2((x[i]-x[c]),(y[i]-y[c]));
if(unghi<0)
unghi+=2*M_PI;
unghi-=uAnt;
if(unghi<0)
unghi+=2*M_PI;
if(minU>unghi)
{
minU=unghi;
poz=i;
}
}
uAnt=atan2(-(x[c]-x[poz]),-(y[c]-y[poz]));
if(uAnt<0)
uAnt+=2*M_PI;
c=poz;
use[c]=1;
}
reverse(v.begin(),v.end());
h=v.size();
out<<h<<"\n";
for(int i=0; i<h; i++)
out<<fixed<<setprecision(6)<<x[v[i]]<<" "<<y[v[i]]<<"\n";
return 0;
}