Pagini recente » Cod sursa (job #458061) | Cod sursa (job #109625) | Cod sursa (job #1476927) | Cod sursa (job #427742) | Cod sursa (job #890868)
Cod sursa(job #890868)
#include<stdio.h>
#include<math.h>
#include<stack>
#define Nmax 120002
using namespace std;
int n;
int viz[Nmax];
float x[Nmax],y[Nmax];
float pi=3.141592;
stack<int> st;
void citire()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%f %f",&x[i],&y[i]);
}
void rezolv()
{
int i,start,poz,next,ok;
float unghi,last,maxim;
start=1;
for(i=2;i<=n;++i)
if(x[start] > x[i])
start=i;
else
if(x[start]==y[start] && y[start] > y[i])
start=i;
poz=start;
next=0;
ok=1;
last=0;
while(ok==1 || poz!=start)
{
ok=0;
st.push(poz);
next=poz;
maxim=-1;
for(i=1;i<=n;++i)
if(viz[i]==0 && i!=poz)
{
unghi=atan2(x[i]-x[poz],y[i]-y[poz]);
if(unghi<0)
unghi+=2*pi;
unghi-=last;
if(unghi<0)
unghi+=2*pi;
if(unghi > maxim)
{
maxim=unghi;
next=i;
}
}
last=atan2(x[next]-x[poz],y[next]-y[poz]);
if(last<0)
last+=2*pi;
poz=next;
viz[poz]=1;
}
}
void scrie()
{
printf("%d\n",st.size());
while(!st.empty())
{
printf("%f %f\n",x[st.top()],y[st.top()]);
st.pop();
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
rezolv();
scrie();
fclose(stdin);
fclose(stdout);
return 0;
}