Pagini recente » Cod sursa (job #1158371) | Cod sursa (job #394652) | Cod sursa (job #1812605) | Cod sursa (job #81060) | Cod sursa (job #3289502)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, i, poz;
pair<double, double> v[120005], aux;
vector<pair<double, double>> st;
int det(pair<double, double> a, pair<double, double> b, pair<double, double> c){
return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
bool cmp(pair<double, double> a, pair<double, double> b){
int d=det({0, 0}, a, b);
if(d!=0){
return d>0;
}else{
return a.first*a.first+a.second*a.second<b.first*b.first+b.second*b.second;
}
}
int main()
{
fin>>n;
for(i=1;i<=n;i++){
fin>>v[i].first>>v[i].second;
}
v[0].first=1005, v[0].second=1005, poz=0;
for(i=1;i<=n;i++){
if(v[i].second<v[poz].second || (v[i].second==v[poz].second && v[i].first<v[poz].first)){
poz=i;
}
}
/*aux=v[1];
v[1]=v[poz];
v[poz]=aux;*/
swap(v[1], v[poz]);
v[0]=v[1];
/*for(i=1;i<=n;i++){
cout<<v[i].first<<" "<<v[i].second<<'\n';
}
cout<<'\n';*/
for(i=1;i<=n;i++){
v[i].first-=v[0].first;
v[i].second-=v[0].second;
}
/*for(i=1;i<=n;i++){
cout<<v[i].first<<" "<<v[i].second<<'\n';
}
cout<<'\n';*/
sort(v+2, v+n+1, cmp);
/*for(i=1;i<=n;i++){
cout<<v[i].first<<" "<<v[i].second<<'\n';
}*/
st.push_back(v[1]), st.push_back(v[2]);
for(i=3;i<=n;i++){
//cout<<v[i].first<<" "<<v[i].second<<'\n';
while(true){
if(det(v[i], st[st.size()-1], st[st.size()-2])>=0 && st.size()>=2){
//if(det(st[st.size()-2], st[st.size()-1], v[i])<0 && st.size()>2){
st.pop_back();
}else{
break;
}
}
st.push_back(v[i]);
}
fout<<st.size()<<'\n';
fout<<setprecision(6)<<fixed;
for(i=0;i<st.size();i++){
fout<<st[i].first+v[0].first<<" "<<st[i].second+v[0].second<<'\n';
}
return 0;
}