Pagini recente » Cod sursa (job #3235992) | Cod sursa (job #417296) | Cod sursa (job #2063012) | Cod sursa (job #2525734) | Cod sursa (job #1124233)
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int l, n, i,ordo, w[120000], k;
float x[120000], y[120000], m[120000], aux;
int isleft( int x1, int y1, int x2, int y2, int x3, int y3)
{
int val=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
return val;
}
void arie()
{
float A;
for(int i=2; i<=k-1; i++) A+=(x[1]*y[w[i]]+x[w[i]]*y[w[i+1]]+x[w[i+1]]*y[1]-x[1]*y[w[i+1]]-x[w[i]]*y[1]-x[w[i+1]]*y[w[i]])/2;
g<<A;
}
int main()
{
f>>n;
for(i=1; i<=n; i++) f>>x[i]>>y[i];
/*l=n;
do{
ordo=1;
for(i=1; i<l; i++)
if(x[i]>x[i+1]) { aux=x[i];
x[i]=x[i+1];
x[i+1]=aux;
aux=y[i];
y[i]=y[i+1];
y[i+1]=aux;
ordo=0;
}
else if(x[i]==x[i+1]) if(y[i]>y[i+1]) {aux=y[i];
y[i]=y[i+1];
y[i+1]=aux;
ordo=0;
}
l--;
} while(!ordo);*/
int val=1;
for(i=1; i<=n; i++) if(x[i]<x[val]) val=i;
else if(x[i]==x[val]&&y[val]>y[i]) val=i;
// g<<val<<'\n';
aux=x[1];
x[1]=x[val];
x[val]=aux;
aux=y[1];
y[1]=y[val];
y[val]=aux;
for(i=2; i<=n; i++)
{if(x[1]-x[i]) m[i]=((y[1]-y[i])/(x[1]-x[i]));
else m[i]=1000000;
}
l=n;
do{
ordo=1;
for(i=2; i<l; i++)
if(m[i]>=m[i+1]) { aux=m[i];
m[i]=m[i+1];
m[i+1]=aux;
aux=x[i];
x[i]=x[i+1];
x[i+1]=aux;
aux=y[i];
y[i]=y[i+1];
y[i+1]=aux;
ordo=0;
}
l--;
} while(!ordo);
w[1]=1;
w[2]=2;
w[3]=3;
k=3;
for(i=4; i<=n; i++)
{ k++;
w[k]=i;
while(k>2 && isleft(x[w[k-2]],y[w[k-2]],x[w[k-1]],y[w[k-1]],x[w[k]],y[w[k]])>=0) {k--; w[k]=i;}
}
g<<k<<'\n';
for(int i=1;i<=k;i++)
g<<x[w[i]]<<" "<<y[w[i]]<<"\n";
//arie();
return 0;
}