Pagini recente » Cod sursa (job #758131) | Cod sursa (job #2227314) | Cod sursa (job #3193772) | Cod sursa (job #1578800) | Cod sursa (job #2777875)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct{
double x, y;
int ind;
};
punct p[120005], pst;
int pst_ind;
vector<punct> st;
double determinant (punct a, punct b, punct c)
{
return a.x*(b.y-c.y) + a.y*(c.x-b.x) + b.x*c.y - c.x*b.y;
}
bool cmp(punct a, punct b)
{
if(determinant(a, pst, b)<0) return 1;
return 0;
}
int main()
{
int n;
fin>>n;
pst.x=1000000000; pst.y=1000000000;
for(int i=0; i<n; i++)
{
fin>>p[i].x>>p[i].y;
p[i].ind=i;
if((p[i].x<pst.x) || (p[i].x==pst.x && p[i].y<pst.y)) pst=p[i], pst_ind=i;
}
swap(p[0], p[pst_ind]);
sort(p+1, p+n, cmp);
st.push_back(pst);
st.push_back(p[1]);
int indst=1;
for(int i=2; i<n; i++)
{
while(determinant(st[indst-1], st[indst], p[i])<0){
indst--;
}
indst++;
if(indst<st.size())
st[indst]=p[i];
else
st.push_back(p[i]);
}
fout<<indst+1<<"\n";
for(int i=0; i<=indst; i++){
fout<<fixed<<setprecision(12)<<st[i].x;
fout<<" ";
fout<<fixed<<setprecision(12)<<st[i].y;
fout<<"\n";
}
return 0;
}