Pagini recente » Cod sursa (job #524262) | Cod sursa (job #3309761) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3310429)
#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 det(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(det(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0){
return 1;
}
if(det(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 gata=0;
while(res.size()>=2&&!gata) {
gata=1;
pair<double,double>alf=res.back();
res.pop_back();
if(det(res.back().x,res.back().y,alf.x,alf.y,v[i].x,v[i].y)<=0) {
gata=0;
} else {
res.push_back(alf);
}
}
res.push_back(v[i]);
}
res.pop_back();
fout<<res.size()<<endl;
for(auto x:res) {
fout<<setprecision(10)<<fixed<<x.x<<' '<<x.y<<'\n';
}
return 0;
}