Pagini recente » Cod sursa (job #2306045) | Cod sursa (job #3160564) | Cod sursa (job #1263759) | Cod sursa (job #1121475) | Cod sursa (job #2756512)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("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)///aria paralelogramului
{
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)///sensul vectorial
{
double crossp=cp(P1,P2,P3);
if(fabs(crossp)<eps)return 0;
if(crossp>-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;
}
int main()
{
int n, i, top;
double a, b;
out << fixed;
in >> n >> a >> b;
P[0].x = a;
P[0].y = b;
for(int i = 1; i< n; ++i)
{
in >> 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;
}
}
out << top << "\n";
for(i = 0; i < top; i++)
{
out << setprecision(6) << P[h[i]].x << " " << setprecision(6) << P[h[i]].y << "\n";
}
return 0;
}