Pagini recente » Cod sursa (job #1018694) | Cod sursa (job #2378401) | Cod sursa (job #2333488) | Cod sursa (job #2876942) | Cod sursa (job #3226700)
#include <fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stack>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
vector<pair<double,double>> vp;
double getCProduct(pair<double,double> v1,pair<double,double> v2){
return v1.first*v2.second-v1.second*v2.first;
}
pair<double,double> makeVector(pair<double,double> p1,pair<double,double> p2){ return {p2.first-p1.first,p2.second-p1.second};}
pair<double,double> po={INT32_MAX,INT32_MAX};
bool isConvex(pair<double,double> p1,pair<double,double> p2){
return getCProduct(makeVector(po,p1),makeVector(p1,p2))>0;
}
bool compare(pair<double,double> p1,pair<double,double> p2){
if(isConvex(p1,p2)){
return true;
}
else if(isConvex(p2,p1)){
return false;
}else {
return (abs(p1.first-po.first)+abs(p1.second-po.second))<(abs(p2.first-po.first)+abs(p2.second-po.second));
}
}
stack<pair<double,double>> sp;
int main()
{
int i,j,nr,n,id;
double x,y;
cin>>n;
for(i=0;i<n;i++){
cin>>x>>y;
vp.push_back({x,y});
if(po>vp[i]){
po=vp[i];
id=i;
}
}
vp.erase(vp.begin()+id);
sort(vp.begin(),vp.end(),compare);
sp.push(po);
sp.push(vp[0]);
for(i=1;i<vp.size();i++){
pair<double,double> p1=sp.top();
sp.pop();
po=sp.top();
if(isConvex(p1,vp[i])){
sp.push(p1);
sp.push(vp[i]);
}
else{
if(sp.size()<2){
sp.push(p1);
}
sp.push(vp[i]);
}
}
cout<<sp.size()<<"\n";
while(!sp.empty()){
auto p=sp.top();
sp.pop();
cout<<p.first<<" "<<p.second<<"\n";
}
return 0;
}