Pagini recente » Cod sursa (job #3032041) | Cod sursa (job #3323728) | Cod sursa (job #411403) | Cod sursa (job #564288) | Cod sursa (job #3301075)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define MAXN 1000007
typedef struct {
int64_t x, y;
} point;
point puncte[MAXN];
point infasuratoare[MAXN];
int N;
int k;
int cmp(const void* a,const void* b)
{
point* p1=(point*)a;
point* p2=(point*)b;
if(p1->x != p2->x)
return (p1->x < p2->x) ? -1 : 1;
else
return (p1->y < p2->y) ? -1 : 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);
}
double calc_arie(point* inf, int size)
{
double arie = 0.0;
for (int i = 0; i < size; ++i)
{
int j = (i + 1) % size;
arie += (double)inf[i].x * inf[j].y - (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, "%" PRId64 " %" PRId64, &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);
k = 0;
for (int i = 0; i < N; i++)
{
while (k >= 2 && prod_vect(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= 0)
k--;
infasuratoare[k++] = puncte[i];
}
int t = k;
for (int i = N - 2; i >= 0; i--)
{
while (k >= t && prod_vect(infasuratoare[k - 2], infasuratoare[k - 1], puncte[i]) <= 0)
k--;
infasuratoare[k++] = puncte[i];
}
k--;
double area = calc_arie(infasuratoare, 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;
}