Pagini recente » Cod sursa (job #2790883) | Cod sursa (job #715197)
Cod sursa(job #715197)
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define NMAX 120010
#define EPS 0.00000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x, y;
}a[NMAX];
int n, vz[NMAX], ord[NMAX+NMAX], aux, S[NMAX];
void Citeste()
{
int i;
f>>n;
for (i=1; i<=n; ++i) f>>a[i].x>>a[i].y;
}
bool cmp(punct A, punct B)
{
if (A.x<B.x || (A.x==B.x && A.y<B.y)) return 1;
return 0;
}
double plan(punct A, punct B, punct C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
void Solve()
{
int m=2, i, j;
double P;
punct aux;
for (i=1, j=2*n; i<=n; ++i, --j)
ord[i]=ord[j]=i;
S[1]=1; S[2]=2; vz[2]=1;
for (i=3; i<=2*n; ++i)
if (!vz[ord[i]])
{
aux=a[ord[i]];
P=plan(a[S[m-1]], a[S[m]], aux);
while (P>=0 && m>1)
{
vz[S[m]]=0; S[m--]=0;
P=plan(a[S[m-1]], a[S[m]], aux);
}
S[++m]=ord[i]; vz[ord[i]]=1;
}
g<<m-1<<"\n";
for (i=m-1; i>0; --i) g<<fixed<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";
}
int main()
{
Citeste();
sort(a+1, a+n+1, cmp);
Solve();
f.close();
g.close();
return 0;
}