Pagini recente » Cod sursa (job #666354) | Cod sursa (job #2741830) | Cod sursa (job #917639) | Cod sursa (job #3359310) | Cod sursa (job #3359326)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
};
bool compar_pct(punct a,punct b)
{
if(abs(a.x-b.x)>1e-12)
{
return a.x<b.x;
}
return a.y<b.y;
}
double produs_vect(punct o,punct a, punct b)
{
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int main (void)
{
int n;
f>>n;
vector<punct> puncte(n);
for(int i=0;i<n;++i)
{
f>>puncte[i].x>>puncte[i].y;
}
sort(puncte.begin(),puncte.end(),compar_pct);
vector<punct> infasurare(2*n);
int k=0;
for(int i=0;i<n;i++)
{
while(k>=2 && produs_vect(infasurare[k-2],infasurare[k-1],puncte[i])<=1e-12)
{
k--;
}
infasurare[k++]=puncte[i];
}
int s=k+1;
for(int i=n-2;i>=0;i--)
{
while(k>=s && produs_vect(infasurare[k-2],infasurare[k-1],puncte[i])<=1e-12)
{
k--;
}
infasurare[k++]=puncte[i];
}
infasurare.resize(k-1);
g<<infasurare.size()<<'\n';
g<<fixed<<setprecision(6);
for(size_t i=0;i<infasurare.size();i++)
{
g<<infasurare[i].x<<" "<<infasurare[i].y<<'\n';
}
return 0;
}