Pagini recente » Cod sursa (job #821495) | Cod sursa (job #1245288) | Cod sursa (job #808839) | Cod sursa (job #785640) | Cod sursa (job #384568)
Cod sursa(job #384568)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 120001
#define pb push_back
using namespace std;
struct pct
{
double a,b;
};
pct v[NMAX];
int n,sol[NMAX],r,ord[NMAX];
vector <int> A[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=i+1; j<=n; 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;
A[i].pb(j);
A[j].pb(i);
}
}
}
void reconst(int poz)
{
printf("%lf %lf\n",v[poz].a,v[poz].b);
marc[poz]=1;
int i,best=0;
for (i=0; i<A[poz].size(); i++)
{
if (!marc[A[poz][i]])
{
//if (!
}
}
}
void show()
{
int i,bestp;
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;
}
}
for (i=1; i<=r; i++)
printf("%lf %lf\n",v[sol[i]].a,v[sol[i]].b);
//reconst(sol[bestp]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve();
show();
return 0;
}