Pagini recente » Cod sursa (job #466783) | Cod sursa (job #729394) | Cod sursa (job #601399) | Cod sursa (job #1123662) | Cod sursa (job #719111)
Cod sursa(job #719111)
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasurtoare.out","w");
typedef struct
{
double x,y;
} xy;
#define MaxN 120010
int N,nr = 2;
xy A[MaxN],S[MaxN];
void citire(void)
{
fscanf(f,"%d ",&N);
for(int i=1;i<=N;i++)
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
}
inline int FirstPoint(void)
{
int P = 1;
for(int i=2;i<=N;i++)
if(A[i].y < A[P].y || (A[i].y == A[P].y && A[i].x < A[P].x))
P = i;
return P;
}
inline void Swap(int a,int b)
{
xy aux = A[a];
A[a] = A[b];
A[b] = aux;
}
inline int cmp(xy a,xy b)
{
return (a.x-A[1].x)/(a.y-A[1].y) > (b.x-A[1].x)/(b.y-A[1].y);
}
inline int IntoarcereDreapta(xy p0,xy p1,xy p2)
{
if(1LL*(p2.x-p0.x)*(p1.y-p0.y)-1LL*(p1.x-p0.x)*(p2.y-p0.y) < 0)
return 1;
return 0;
}
void Rezolvare(void)
{
Swap(1,FirstPoint());
sort(A+2,A+N+1,cmp);
S[1] = A[1];
S[2] = A[2];
for(int i=3;i<=N;i++)
{
while(!IntoarcereDreapta(S[nr-1],S[nr],A[i]))
-- nr;
S[++nr] = A[i];
}
}
void Afisare(void)
{
fprintf(g,"%d\n",nr);
for(int i=1;i<=nr;i++)
fprintf(g,"%.6lf %.6lf\n",S[i].x,S[i].y);
}
int main()
{
citire();
Rezolvare();
Afisare();
}