Pagini recente » Cod sursa (job #3357976) | Cod sursa (job #2146308) | Cod sursa (job #1242787) | Cod sursa (job #2189767) | Cod sursa (job #3309767)
#include <fstream>
#include<deque>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>v[120022];
vector<pair<double,double>>res;
double deter(double x1,double y1,double x2,double y2,double x3,double y3){
return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
}
bool comp(pair<double,double>a,pair<double,double>b){
if(deter(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0)return 1;
if(deter(v[0].x,v[0].y,a.x,a.y,b.x,b.y)<0)return 0;
return a.x<b.x;
}
signed main()
{
int n;
fin>>n;
fin>>v[0].x>>v[0].y;
for(int i=1;i<n;i++){
fin>>v[i].x>>v[i].y;
if(v[i].x<v[0].x || (v[i].x==v[0].x && v[i].y < v[0].y))swap(v[0],v[i]);
}
v[n]=v[0];
sort(v+1,v+n,comp);
res.push_back(v[0]);
for(int i=1;i<=n;i++){
bool lb=1;
while(res.size()>=2 && lb){
lb=0;
pair<double,double>alf=res.back();
res.pop_back();
if(deter(res.back().x,res.back().y,alf.x,alf.y,v[i].x,v[i].y)<=0)lb=1;
else res.push_back(alf);
}
res.push_back(v[i]);
}
res.pop_back();
fout<<res.size()<<endl;
for(auto x:res){
fout<<setprecision(8)<<fixed<<x.x<<" "<<x.y<<endl;
}
return 0;
}