Pagini recente » Cod sursa (job #2453889) | Cod sursa (job #2106779) | Cod sursa (job #417048) | Cod sursa (job #185944) | Cod sursa (job #871246)
Cod sursa(job #871246)
#include<cstdio>
#include<fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120001
using namespace std;
struct punct
{
double x,y;
};
punct P[nmax],ST[nmax];
int N,M;
bool comp(punct A,punct B)
{
if(A.x<B.x)
return true;
else
if(A.x==B.x && A.y<B.y)
return true;
return false;
}
double delta(punct &p1,punct &p2,punct &p3)
{
return(
(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
}
void citeste()
{
FILE *f=fopen("infasuratoare.in","r");
int i;
fscanf(f,"%d",&N);
for(i=1;i<=N;i++)
fscanf(f,"%lf %lf",&P[i].x,&P[i].y);
fclose(f);
}
void rezolva()
{
int i,t;
sort(P+1,P+N+1,comp);
ST[1]=P[1];
ST[2]=P[2];
M=2;
for(i=3;i<=N;i++)
{
while(M>=2 && delta(ST[M-1],ST[M],P[i])<=0)
--M;
ST[++M]=P[i];
}
for(i=N-1;i>=1;i--)
{
while(M>=2 && delta(ST[M-1],ST[M],P[i])<=0)
--M;
ST[++M]=P[i];
}
}
void scrie()
{
ofstream g("infasuratoare.out");
int i;
g<<M-1<<'\n';
g<<fixed;
g<<setprecision(6);
for(i=1;i<=M-1;i++)
g<<ST[i].x<<' '<<ST[i].y<<'\n';
g.close();
}
void scrie2()
{
FILE *g=fopen("infasuratoare.out","w");
fprintf(g,"%d\n",M-1);
for(int i=1;i<=M-1;i++)
fprintf(g,"%lf %lf\n",ST[i].x,ST[i].y);
fclose(g);
}
int main()
{
citeste();
rezolva();
scrie2();
return 0;
}