Pagini recente » Cod sursa (job #273628) | Cod sursa (job #3329902) | Atasamentele paginii Profil icecool10 | Borderou de evaluare (job #1026843) | Cod sursa (job #3301072)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.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)
{
if(p1->x<p2->x)return -1;
else return 1;
}
else
{
if(p1->y<p2->y)return -1;
else 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);
}
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, "%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);
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 + 1;
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;
}