Pagini recente » Cod sursa (job #568710) | Cod sursa (job #3194197) | Cod sursa (job #1157108) | Cod sursa (job #1955180) | Cod sursa (job #3001207)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include<iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct punct{
float x,y;
}puncte[120001];
punct pct_minim;
int indice_min;
vector<punct>st;
float det(punct a,punct b,punct c)
{
float det = a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-b.x*a.y-c.y*a.x;
return det;
}
bool cmp(punct a,punct b)
{
if(det(pct_minim,a,b)>0)
return true;
return false;
}
bool sens_ceas(punct a,punct b,punct c)
{
if(det(a,b,c)<=0)
return 1;
return 0;
}
void gasire_punct()
{
pct_minim.x = 2000000000.00;
pct_minim.y=2000000000.00;
for(int i = 1;i<=n;i++)
{
if(pct_minim.x>puncte[i].x)
{
pct_minim = puncte[i];
indice_min = i;
}
else
if(pct_minim.x==puncte[i].x && pct_minim.y>puncte[i].y)
{
pct_minim.y = puncte[i].y;
indice_min = i;
}
}
}
int main()
{
f >> n;
for(int i = 1;i<=n;i++)
{
f >> puncte[i].x>> puncte[i].y;
}
gasire_punct();
swap(puncte[1],puncte[indice_min]);
sort(puncte+2,puncte+1+n,cmp);
st.push_back(puncte[1]);
st.push_back(puncte[2]);
for(int i =3;i<=n;i++)
{
while(!sens_poz(st[st.size()-2],st[st.size()-1],puncte[i]))
{
st.pop_back();
}
st.push_back(puncte[i]);
}
g << st.size()<<'\n';
int l = st.size();
for(int i =0;i<l;i++)
g << fixed<< setprecision(6)<< st[i].x << " "<< setprecision(6)<< st[i].y<< "\n";
}