Pagini recente » Monitorul de evaluare | Cod sursa (job #1343674) | Cod sursa (job #1006567) | Cod sursa (job #1560396) | Cod sursa (job #384569)
Cod sursa(job #384569)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 120001
using namespace std;
struct pct
{
double a,b;
};
pct v[NMAX];
int n,sol[NMAX],r,ord[NMAX];
int A[NMAX],B[NMAX];
double a,b,c;
char viz[NMAX],marc[NMAX];
void read()
{
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%lf%lf",&v[i].a,&v[i].b);
}
inline int sign(int k)
{
double rez=v[k].a*a-v[k].b*b+c;
if (rez<=0)
return 0;
return 1;
}
void solve()
{
int i,j,k;
char tip,tb,ok;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i!=j)
{
tb=5; ok=1;
a=v[i].b-v[j].b;
b=v[i].a-v[j].a;
c=v[i].a*v[j].b-v[j].a*v[i].b;
for (k=1; k<=n; k++)
if (k!=i && k!=j)
{
tip=sign(k);
if (tb==5)
tb=tip;
else
if (tb!=tip)
{
ok=0;
break;
}
}
if (ok)
{
if (!viz[i])
{
sol[++r]=i,viz[i]=1;
}
if (!viz[j])
sol[++r]=j,viz[j]=1;
if (!A[i])
A[i]=j;
else
B[i]=j;
if (!A[j])
A[j]=i;
else
B[j]=i;
}
}
}
void show()
{
int i,bestp,j,pozitie;
printf("%d\n",r);
double x,y;
x=v[sol[1]].a; y=v[sol[1]].b; bestp=1;
for (i=2; i<=r; i++)
{
if (v[sol[i]].b==y && v[sol[i]].a<x)
{
x=v[sol[i]].a;
bestp=i;
}
if (v[sol[i]].b<y)
{
y=v[sol[i]].b;
x=v[sol[i]].a;
bestp=i;
}
}
printf("%lf %lf\n",v[sol[bestp]].a,v[sol[bestp]].b);
j=sol[bestp];
marc[j]=1;
a=v[j].b-v[A[j]].b;
b=v[j].a-v[A[j]].a;
c=v[j].a*v[A[j]].b-v[A[j]].a*v[j].b;
int ans1=sign(B[j]);
a=v[j].b-v[B[j]].b;
b=v[j].a-v[B[j]].a;
c=v[j].a*v[B[j]].b-v[B[j]].a*v[j].b;
int ans2=sign(A[j]);
if (ans1)
pozitie=A[j];
else
pozitie=B[j];
while (1)
{
printf("%lf %lf\n",v[pozitie].a,v[pozitie].b);
marc[pozitie]=1;
if (!marc[A[pozitie]])
pozitie=A[pozitie];
if (!marc[B[pozitie]])
pozitie=B[pozitie];
if (marc[A[pozitie]] && marc[B[pozitie]])
{
if (!marc[A[j]])
printf("%lf %lf\n",v[A[j]].a,v[A[j]].b);
else
printf("%lf %lf\n",v[B[j]].a,v[B[j]].b);
return ;
}
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve();
show();
return 0;
}