Pagini recente » Cod sursa (job #1875514) | Cod sursa (job #1655868) | Cod sursa (job #1582267) | Cod sursa (job #1181579) | Cod sursa (job #448907)
Cod sursa(job #448907)
#include <cstdio>
#include <algorithm>
#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;
FILE *in=fopen("infasuratoare.in", "r");
fscanf(in, "%d", &n);
for(int i=0; i<n; ++i)
{
fscanf(in, "%lf%lf", &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)
{
FILE *out=fopen("infasuratoare.out", "w");
fprintf(out, "%d\n", n);
for(int i=0; i<n; ++i)
fprintf(out, "%.6lf %.6lf\n", a[i].x, a[i].y);
}
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;
}