Pagini recente » Cod sursa (job #1267866) | Cod sursa (job #1188328) | Cod sursa (job #1864917) | Cod sursa (job #828663) | Cod sursa (job #2194745)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
const int NMAX = 120005;
const double EPS = 1e-12;
pair<double,double> V[NMAX];
bool Use[NMAX];
int ST[NMAX];
int Front;
void Read()
{
fin>>N;
for(int i=1;i<=N;i++)
{
fin>>V[i].first>>V[i].second;
}
}
double product(pair<double,double> O,pair<double,double> A, pair<double,double> B)
{
return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second);
}
int main()
{
Read();
sort(V+1,V+N+1);
ST[1] = 1;
ST[2] = 2;
Front = 2;
Use[2] = true;
for(int i=1,p=1; i > 0; i+= (p = (i == N? -p : p)))
{
if (Use[i])continue;
while(Front >= 2 && product(V[ST[Front-1]], V[ST[Front]],V[i]) < EPS)
Use[ST[Front--]] = false;
ST[++Front] = i;
Use[i] = true;
}
fout<<Front - 1<<'\n';
fout<<setprecision(6)<<fixed;
for(int i=1;i<Front;i++)
{
fout<<V[ST[i]].first<<' '<<V[ST[i]].second<<'\n';
}
return 0;
}