Pagini recente » Cod sursa (job #3353007) | Cod sursa (job #3312466) | Cod sursa (job #3343597) | Cod sursa (job #303322) | Cod sursa (job #3301068)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define MAXN 1000007
typedef struct{
int64_t x,y;
} point;
point punct[MAXN];
point infasuratoare[MAXN];
int N;
int cmp(const void* a,const void* b)
{
point* p1=(point*)a;
point* p2=(point*)b;
if(p1->x<p2->x)return -1;
return 1;
}
int64_t prod_vect(point O,point A,point B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
long double calc_arie(point* inf,int size)
{
long double arie = 0.0;
for (int i = 0; i < size; ++i)
{
int j = (i + 1) % size;
arie += (long double)inf[i].x * inf[j].y - (long double)inf[j].x * inf[i].y;
}
if (arie < 0) arie = -arie;
return arie / 2.0;
}
int main(void)
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
if (fin == NULL || fout == NULL)
{
fprintf(stderr, "eroare la deschiderea fisierelor");
exit(EXIT_FAILURE);
}
if (fscanf(fin, "%d", &N) != 1)
{
fprintf(stderr, "eroare la citirea numarului de puncte");
exit(EXIT_FAILURE);
}
for (int i = 0; i < N; ++i)
{
if (fscanf(fin, "%ld %ld", &puncte[i].x, &puncte[i].y) != 2)
{
fprintf(stderr, "eroare la citirea punctului %d\n", i);
exit(EXIT_FAILURE);
}
}
qsort(puncte,N,sizeof(point),cmp);
for(int i=0;i<N;i++)
{
while(k>=2 && prod_vect(infasuratoare[k-2],infasuratoare[k-1],infasuratoare[k])<=0)
{
k--;
}
infasuratoare[k++]=puncte[i];
}
k--;
long double area = calc_area(hull, k);
fprintf(fout, "%.4Lf\n", area);
if (fclose(fin) != 0)
{
fprintf(stderr, "eroare la inchiderea fisierului de citire");
exit(EXIT_FAILURE);
}
if (fclose(fout) != 0)
{
fprintf(stderr, "eroare la inchiderea fisierului de scriere");
exit(EXIT_FAILURE);
return 0;
}