Pagini recente » Cod sursa (job #986997) | Cod sursa (job #2603674) | Cod sursa (job #2719240) | Cod sursa (job #1020557) | Cod sursa (job #2535682)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
bool operator <(punct a)
{
if(a.x==x)
return (a.y>y);
return (a.x>x);
}
};
int n;
vector <punct> v;
vector <punct> V;
vector <punct> B;
void citire()
{
fin>>n;
v.reserve(n);
for(int i=0; i<n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v.begin(),v.end());
}
int det(punct a,punct b,punct c)
{
if((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)>0)
return 1;
else return -1;
}
void infasuratoare()
{
V.push_back(v[0]);
V.push_back(v[1]);
int k=2;
for(int i=2; i<n; i++)
{
while(k > 1 && det(V[k-2],V[k-1],v[i])==-1)
{
V.pop_back();
k--;
}
V.push_back(v[i]);
k++;
}
B.push_back(v[n-1]);
B.push_back(v[n-2]);
int aux=2;
for(int i=n-3; i>=0; i--)
{
while(aux>1&&det(B[aux-2],B[aux-1],v[i])==-1)
{
B.pop_back();
aux--;
}
B.push_back(v[i]);
aux++;
}
fout<<k+aux-2<<"\n";
for(int i=0; i<k; i++)
{
fout<<setprecision(6)<<fixed;
fout<<V[i].x<<" "<<V[i].y<<"\n";
}
for(int i=1; i<aux-1; i++)
{
fout<<setprecision(6)<<fixed;
fout<<B[i].x<<" "<<B[i].y<<"\n";
}
}
int main()
{
citire();
infasuratoare();
return 0;
}