Pagini recente » Cod sursa (job #1008665) | Cod sursa (job #2985487) | Cod sursa (job #265290) | Cod sursa (job #2410690) | Cod sursa (job #448878)
Cod sursa(job #448878)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define cxinf 9999999999.99999
#define MAX 120002
using namespace std;
struct point
{
double x, y;
}P, a[MAX], s[MAX];
void read(point a[], int &n)
{
P.x=P.y=cxinf;
fstream fin("infasuratoare.in", ios::in);
fin>>n;
for(int i=1; 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];
}
}
void write(point a[], int n)
{
fstream fout("infasuratoare.out", ios::out);
setprecision(12);
fout << setiosflags(ios::fixed) << n+1 << "\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);
}
bool operator!=(point A, point B)
{
return ((A.x-B.x) || (A.y-B.y));
}
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[], point stack[], int n)
{
int vertex=2;
stack[0]=P;
stack[1]=a[1];
for(int i=2; i<=n; ++i)
{
if(a[i]!=P)
{
while(angle(stack[vertex-2], stack[vertex-1], a[i])<0)
vertex--;
stack[vertex++]=a[i];
}
}
return vertex;
}
int main()
{
int n, hn;
read(a, n);
sort(a+1, a+n+1);
a[0]=P;
hn=hull(a, s, n);
write(s, hn-1);
return 0;
}