Pagini recente » Cod sursa (job #2969171) | Cod sursa (job #159319) | Cod sursa (job #2279167) | Cod sursa (job #936987) | Cod sursa (job #2878117)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct p
{
double x,y;
};
p v[120001];
double cmp(p a,p b)
{
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
double calc(double xa,double ya,double xb,double yb, double xc,double yc)
{
return (xa*yb+xb*yc+xc*ya-yc*xa-yb*xc-xb*ya)/2.0;
}
int n;
p stiva[120001];
p stiva1[120001];
int k;
int k1;
int main()
{
fin >>n;
for (int i=1; i<=n; i++)
{
fin >>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
int i=2;
stiva[++k].x=v[1].x;
stiva[k].y=v[1].y;
while (i<=n)
{
if (k<2)
{
if (calc(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)<0)
{
stiva[++k].x=v[i].x;
stiva[k].y=v[i].y;
}
}
else
{
while (calc(stiva[k-1].x,stiva[k-1].y,stiva[k].x,stiva[k].y,v[i].x,v[i].y)<0 && k>=2)
{
k--;
}
stiva[++k].x=v[i].x;
stiva[k].y=v[i].y;
}
i++;
}
i=1;
stiva1[++k1].x=v[1].x;
stiva1[k1].y=v[1].y;
while (i<=n)
{
if (k1<2)
{
if (calc(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)>0)
{
stiva1[++k1].x=v[i].x;
stiva1[k1].y=v[i].y;
}
}
else
{
while (calc(stiva1[k1-1].x,stiva1[k1-1].y,stiva1[k1].x,stiva1[k1].y,v[i].x,v[i].y)>0 && k1>=2)
{
k1--;
}
stiva1[++k1].x=v[i].x;
stiva1[k1].y=v[i].y;
}
i++;
}
fout << k1+k-2 <<"\n";
fout << v[1].x <<" "<<v[1].y <<"\n";
for (int j=2; j<=k-1; j++) fout << stiva[j].x <<" "<<stiva[j].y<<"\n";
fout <<v[n].x <<" "<<v[n].y<<"\n";
for (int j=k1-1; j>=2; j--) fout << stiva1[j].x <<" "<<stiva1[j].y<<"\n";
fout <<"\n";
}