Pagini recente » Cod sursa (job #2880140) | Cod sursa (job #3350702) | Cod sursa (job #1558025) | Borderou de evaluare (job #2504165) | Cod sursa (job #3300626)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 120005 //putin mai mare ca N-ul maxim
typedef struct{
double x, y;
}Point;
Point p[MAXN];//vectorul de puncte
int st[MAXN];
int n,sz;//n e numarul de puncte date de problema si sz e numarul de puncte pe care le folosim
double orientation(Point a, Point b, Point c)//calculeaza determinantul pentru a determina orientarea(practic unghiul)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
double manhattan(Point a, Point b)//distanta Manhattan, e mai simplu ca cea euclidiana
{
return fabs(a.x-b.x)+fabs(a.y-b.y);
}
int cmp(const void* A, const void* B)//functie de comparare pt qsort, compara unghiurile celor 2 puncte cu punctul de start
{
Point a=*(Point*)A;
Point b=*(Point*)B;
double orient=orientation(p[0],a,b);
if (fabs(orient)<1e-12)
{
if (a.x!=b.x)
return (a.x<b.x)?-1:1;
return (a.y<b.y)?-1:1;
}
return (orient>0)?-1:1;
}
void find_lowest()//functia care gaseste cel mai din stanga punct, in caz de egalitate a 2 x-uri ia y-ul mai mic
{
int ind=0;
for (int i=1;i<n;i++)
{
if (p[i].x<p[ind].x || (p[i].x==p[ind].x && p[i].y<p[ind].y))
{
ind=i;
}
}
Point tmp=p[0];
p[0]=p[ind];//schimba primul punct din lista cu cel gasit ca cel mai in stanga-jos
p[ind]=tmp;
}
void sort_points()//sorteaza punctele in mod eficient
{
qsort(p+1,n-1,sizeof(Point),cmp);
}
void convex_hull()//folosim algoritmul graham scan
{
sz=0;
for(int i=0; i<n;i++)
{
while (sz>=2 && orientation(p[st[sz-2]],p[st[sz-1]],p[i])<=1e-12)
sz--;
st[sz++]=i;
}
}
int main(void)
{
FILE *fin=fopen("infasuratoare.in", "r");
FILE *fout=fopen("infasuratoare.out", "w");
if(fin==NULL)//verificam deschiderea fisierelor
{
perror("Eroare la deschiderea fisierului de citire.\n");
exit(1);
}
if(fout==NULL)
{
perror("Eroare la deschiderea fisierului de scriere.\n");
exit(1);
}
if(fscanf(fin, "%d", &n)!=1)//citim numarul n de puncte
{
perror("Eroare la citirea din fisier.\n");
exit(1);
}
for (int i=0;i<n;i++) //apoi citim cele n puncte
{
if(fscanf(fin, "%lf %lf", &p[i].x, &p[i].y)!=2)
{
perror("Eroare la citirea din fisier.\n");
exit(1);
}
}
find_lowest();//gasim cel mai din stanga-jos punct(startul)
sort_points();
convex_hull();//cautam ce puncte ne trebuie si le salvam in vector dar si schimbam sz-ul de fiecare data cand gasim un punct
fprintf(fout,"%d\n",sz);//scriem cate laturi si care laturi sunt incluse
for (int i=0;i<sz;i++)
{
fprintf(fout,"%.12lf %.12lf\n",p[st[i]].x,p[st[i]].y);
}
if(fclose(fin)!=0)//verificam inchiderea fisierelor
{
perror("Eroare inchidere fisier citire.\n");
exit(1);
}
if(fclose(fout)!=0)
{
perror("Eroare inchidere fisier scriere.\n");
exit(1);
}
return 0;
}