Pagini recente » Cod sursa (job #1554249) | Cod sursa (job #2783831) | Cod sursa (job #2620014) | Cod sursa (job #3180939) | Cod sursa (job #1154231)
#include <stdio.h>
#include <vector>
#include <bitset>
#include <algorithm>
#define In "infasuratoare.in"
#define Out "infasuratoare.out"
#define Nmax 120010
#define eps 1e-12
using namespace std;
int N,St[Nmax], top;
pair<double,double> A[Nmax];
bitset< Nmax >use;
inline void Read()
{
FILE * FIN = fopen(In,"r");
fscanf(FIN,"%d",&N);
for(int i = 1; i <= N; ++i)
fscanf(FIN,"%lf %lf",&A[i].first,&A[i].second);
fclose(FIN);
sort(A+1,A+N+1);
}
inline float Semn(int i,int j,int k)
{
return (A[j].first-A[i].first)*(A[k].second-A[i].second)-(A[j].second-A[i].second)*(A[k].first-A[i].first);
}
inline void Solve()
{
int i,x = 1;
St[++top] = 1;St[++top] = 2;
use[2] = true;
for(i = 3 ;i>0; i += x)
{
if(!use[i])
{
while(top>=2 && Semn(St[top-1],St[top],i) < eps )
{
use[St[top]] = 0;
--top;
}
St[++top] = i;
use[i] = 1;
}
if(i==N)
x = -1;
}
}
inline void Write()
{
FILE * FOUT = fopen(Out,"wt");
fprintf(FOUT,"%d\n",top-1);
for(int i=1;i<top;++i)
fprintf(FOUT,"%.6lf %.6lf\n",A[St[i]].first,A[St[i]].second);
fclose(FOUT);
}
int main()
{
Read();
Solve();
Write();
return 0;
}