Pagini recente » Cod sursa (job #54336) | Cod sursa (job #2538697) | Cod sursa (job #1588383) | Cod sursa (job #2042309) | Cod sursa (job #952745)
Cod sursa(job #952745)
#include <fstream>
#include <cmath>
#include <cstdio>
#define maxn 120001
using namespace std;
ifstream f("infasuratoare.in");
int n;
struct punct
{
float x,y;
}p[maxn];
int inf[maxn];
float len(int i,int j)
{
return sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x) + (p[j].y-p[i].y)*(p[j].y-p[i].y));
}
float angle(int i, int j, int k)
{
float unghi,a1,a2,b1,b2,l1,l2;
a1=p[j].x-p[i].x;
b1=p[j].y-p[i].y;
a2=p[k].x-p[i].x;
b2=p[k].y-p[i].y;
l1=len(i,j);
l2=len(i,k);
unghi=acos((a1*a2+b1*b2)/(l1*l2))*(180/M_PI);
if(unghi<0) unghi=unghi+2*M_PI;
return unghi;
}
int main()
{
freopen("infasuratoare.out","w",stdout);
f>>n;
int i,mini;
for(i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
mini=1;
for(i=1;i<=n;i++)
{
if(p[i].x<p[mini].x) mini=i;
else if(p[i].x==p[mini].x)
if(p[i].y<p[mini].y) mini=i;
}
p[0].x=p[mini].x;
p[0].y=p[mini].y-1;
int k=1;
float unghi,maxu;
int curr=mini; int prec=0;
int wini;
do
{
inf[k++]=curr;
maxu=-1;
for(i=1;i<=n;i++)
{
if(i==curr || i==prec) continue;
unghi=angle(curr,i,prec);
if(maxu<unghi) {maxu=unghi; wini=i;}
}
prec=curr;
curr=wini;
}while(curr!=mini);
printf("%d\n",k-1);
for(i=k-1;i;i--)
{
printf("%lf %lf\n",p[inf[i]].x,p[inf[i]].y);
}
}