Pagini recente » Cod sursa (job #2974409) | Cod sursa (job #2931227) | Cod sursa (job #1939415) | Cod sursa (job #2385511) | Cod sursa (job #448904)
Cod sursa(job #448904)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define cxinf 999999999.99999
#define MAX 120002
using namespace std;
struct point
{
double x, y;
}P, a[MAX];
void read(point a[], int &n)
{
P.x=P.y=cxinf;
fstream fin("infasuratoare.in", ios::in);
fin>>n;
for(int i=0; i<n; ++i)
{
fin>>a[i].x>>a[i].y;
if(P.x>a[i].x || (P.x==a[i].x && P.y>a[i].y))
{
P=a[i];
swap(a[0], a[i]);
}
}
}
void write(point a[], int n)
{
fstream fout("infasuratoare.out", ios::out);
setprecision(12);
fout << setiosflags(ios::fixed) << n << "\n";
for(int i=0; i<n; ++i)
fout << a[i].x << " " << a[i].y << "\n";
}
bool operator<(point A, point B)
{
return (((A.y-P.y)*(B.x-P.x)-(B.y-P.y)*(A.x-P.x))<0);
}
double angle(point p1, point p2, point p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int hull(point a[], int n)
{
int vertex=2;
for(int i=2; i<n; ++i)
{
while(angle(a[vertex-2], a[vertex-1], a[i])<0)
vertex--;
a[vertex++]=a[i];
}
return vertex;
}
int main()
{
int n, hn;
read(a, n);
sort(a+1, a+n);
hn=hull(a, n);
write(a, hn);
return 0;
}