Pagini recente » Cod sursa (job #3172164) | Cod sursa (job #2162716) | Cod sursa (job #2194143) | Cod sursa (job #2929724) | Cod sursa (job #2756510)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
const double eps=1.0e-14;
const double INF=1e9;
const int NMAX=120000;
struct POINT
{
double x, y;
};
POINT P[NMAX+5], LL;
int h[NMAX+5];
double cp(const POINT& P1, const POINT& P2, const POINT& P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(const POINT& P1, const POINT& P2, const POINT& P3)
{
double crossprod=cp(P1, P2, P3);
if (fabs(crossprod)<eps)
return 0;
if (crossprod>=eps)
return 1;
return -1;
}
bool cmp(POINT& P1, POINT& P2)
{
return ccw(LL, P1, P2)>0;
}
double arie_poligon(int n)
{
double aria;
int i;
P[n]=P[0];
aria=0;
for (i=0; i<n; i++)
aria=P[i].x*P[i+1].y-P[i+1].x*P[i].y;
aria=0.5*fabs(aria);
return aria;
}
using namespace std;
int main()
{
int n, i, top;
double a, b;
fout<<fixed;
fin>>n>>a>>b;
P[0].x=a;
P[0].y=b;
for (i=1; i<n; i++)
{
fin>>a>>b;
P[i].x=a;
P[i].y=b;
if (P[i].y-P[0].y<=-eps || ((fabs(P[i].y-P[0].y)<eps) && (P[i].x-P[0].x<=-eps)))
swap(P[i], P[0]);
}
LL=P[0];
P[n]=P[0];
h[0]=0;
h[1]=1;
sort(P+1, P+n, cmp);
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';
for (i=0; i<top; i++)
fout<<setprecision(6)<<P[h[i]].x<<' '<<setprecision(6)<<P[h[i]].y<<'\n';
return 0;
}