Pagini recente » Cod sursa (job #645384) | Cod sursa (job #1403162) | Cod sursa (job #3289553) | Cod sursa (job #601081) | Cod sursa (job #952742)
Cod sursa(job #952742)
#include <fstream>
#include <cmath>
#define maxn 120001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
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()
{
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);
g<<k-1<<'\n';
for(i=k-1;i;i--)
{
g<<p[inf[i]].x<<' '<<p[inf[i]].y<<'\n';
}
}