Pagini recente » Cod sursa (job #2794695) | Cod sursa (job #674833) | Cod sursa (job #3155248) | Cod sursa (job #690201) | Cod sursa (job #2355978)
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
int P;
struct PCT
{
double x,y;
};
PCT lst[120010];
int N;
int st[120010],added[120010];
bool Critery(PCT A,PCT B)
{
if(A.y!=B.y) return (A.y<B.y);
return (A.x<B.x);
}
void Read()
{
int I;
fscanf(f,"%d",&N);
for(I=1;I<=N;++I)
fscanf(f,"%lf %lf",&lst[I].x,&lst[I].y);
sort(lst+1,lst+1+N,Critery);
}
struct Puncte
{
double x,y;
};
Puncte A,B,C;
int Pozitionare(int p1,int p2,int p3)///dacă determinantul este negativ, punctele sunt puse în ordine trigonometrică
{
double det;
A.x=lst[p1].x;A.y=lst[p1].y;
B.x=lst[p2].x;B.y=lst[p2].y;
C.x=lst[p3].x;C.y=lst[p3].y;
det=(A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-C.y*A.x-A.y*B.x);
return det;
}
int nr;
void Solve()
{
int I=3,unitate=1;
st[1]=1,st[2]=2;added[2]=1;
nr=2;
while(!added[1])///atâta timp cât nu m-am întors înapoi la primul element
{
while(added[I])///caut un nou punct și încerc să-l dadaug în înfășurătoare
{
if(I==N)unitate=-1;///am ajuns în vârf, deci mă întorc
I+=unitate;
}
while(nr>=2&&Pozitionare(st[nr],st[nr-1],I)>0)///elimin punctele care nu respectă ordinea trigonometrică
added[st[nr--]]=0;
st[++nr]=I;added[I]=1;
}
}
void Displaying()
{
int i;
fprintf(g,"%d\n",nr-1);
for(i=1;i<=nr-1;++i)
fprintf(g,"%lf %lf\n",lst[st[i]].x,lst[st[i]].y);
}
int main()
{
f=fopen("infasuratoare.in","r");g=fopen("infasuratoare.out","w");
Read();Solve();Displaying();
fclose(f);fclose(g);
return 0;
}