Pagini recente » Cod sursa (job #2074347) | Cod sursa (job #306088) | Cod sursa (job #2108692) | Cod sursa (job #853589) | Cod sursa (job #2569702)
#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 crossproduct(ceva a,ceva b)
{
return a.x*b.y-a.y*b.x;
}
int ok(int i,int poz,int poz2)
{
return (i!=poz && i!=poz2 && v[i].viz==0);
}
int get_unghi(ceva a,ceva b,ceva c)
{
double ab,ac,bc;
ab=crossproduct(a,b);
bc=crossproduct(b,c);
ac=crossproduct(a,c);
return (ab*ab+ac*ac-bc*bc)/(2*ab*ac);
}
void get_infasuratoare(ceva a,ceva b,int poz,int poz2)
{
if(poz2==pozinit)
return;
int pozitie=0,unghimax=-10000,unghi=0,altok=0;
for(i=1;i<=n;i++)
if(ok(i,poz,poz2))
{
altok=1;
unghi=abs(get_unghi(a,b,v[i]));
if(unghi>unghimax)
unghimax=unghi , pozitie=i;
}
if(altok==0)
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].y<v[poz].x || poz==0)
poz=i;
else if(v[i].y==v[poz].y && v[i].x<v[poz].x)
poz=i;
}
sol[++nr].x=v[poz].x;
sol[nr].y=v[poz].y;
pozinit=poz;
get_infasuratoare(v[poz],{v[poz].x,v[poz].y+10,0},poz,0);
fout<<nr<<'\n';
for(i=1;i<=nr;i++)
fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<'\n';
return 0;
}