Pagini recente » Cod sursa (job #887727) | Cod sursa (job #679700) | Cod sursa (job #929474) | Cod sursa (job #624275) | Cod sursa (job #3221862)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps=1.0e-12;
struct POINT
{
double x,y;
};
const int NMAX=120000;
POINT P[NMAX+5];
POINT LL;
int h[NMAX+5];
double cp(POINT A, POINT B, POINT C)
{
return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}
int ccw(POINT A, POINT B, POINT C)
{
/*0 daca abc sunt coliniare
1 daca c este in sens trigonometric fata de ab (la stanga)
-1 daca este in sens orar fata de ab (la dreapta)
*/
double cpp = cp(A, B, C);
if(fabs(cpp) < eps)
return 0;
if(cpp >= eps)
return 1;
return -1;
}
bool cmp(POINT A, POINT B)
{
return ccw(LL,A,B)>0;
}
int main()
{
int n, i, top;
double tx, ty;
fin >> n;
fin >> tx >> ty;
LL.x=tx;
LL.y=ty;
P[0]=LL;
for(i=1; i<n; ++i)
{
fin >> tx >> ty;
P[i].x=tx;
P[i].y=ty;
if(LL.y-ty>eps || fabs(LL.y-ty)<eps && LL.x-tx>eps)
{
P[i]=LL;
LL.x=tx;
LL.y=ty;
P[0]=LL;
}
}
sort(P+1,P+n,cmp);
P[n]=LL;
h[0]=0;
h[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
fout << top << "\n";
fout << showpoint << fixed << setprecision(6);
for(i=0; i<top; ++i)
fout << P[h[i]].x << " " << P[h[i]].y << "\n";
fin.close();
fout.close();
return 0;
}