Pagini recente » Borderou de evaluare (job #1569284) | Cod sursa (job #652013) | Cod sursa (job #2333383) | Cod sursa (job #2815248) | Cod sursa (job #2571173)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct ceva
{
double x,y;
bool viz;
}v[120010],sol[120010];
int n,i,poz,nr,pozinit;
int dist(ceva a,ceva b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int ok(int i,int poz,int poz2)
{
return (i!=poz && i!=poz2 && v[i].viz==0);
}
double get_unghi(ceva a,ceva b,ceva c)
{
double ab,ac,bc;
ab=dist(a,b);
bc=dist(b,c);
ac=dist(a,c);
return (acos((ab*ab+bc*bc-ac*ac)/(2*ab*bc)))*180/3.1415;
}
void get_infasuratoare(ceva a,ceva b,int poz,int poz2)
{
if(poz2==pozinit)
return;
int pozitie=0;
double unghimax=-10000,unghi=0,altok=0;
for(i=1;i<=n;i++)
{
altok=1;
unghi=get_unghi(a,b,v[i]);
if(unghi>=unghimax)
unghimax=unghi , pozitie=i;
}
if(v[pozitie].viz==1)
return;
sol[++nr].x=v[pozitie].x;
sol[nr].y=v[pozitie].y;
v[pozitie].viz=true;
get_infasuratoare(b,v[pozitie],poz,pozitie);
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].x<v[poz].x || poz==0)
poz=i;
else if(v[i].x==v[poz].x && v[i].y<v[poz].y)
poz=i;
}
v[poz].viz=1;
sol[++nr].x=v[poz].x;
sol[nr].y=v[poz].y;
pozinit=poz;
get_infasuratoare({v[poz].x+10,v[poz].y,0},v[poz],poz,0);
fout<<nr<<'\n';
for(i=nr;i>=1;i--)
fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<'\n';
return 0;
}