Pagini recente » Adunarea jocurilor | Cod sursa (job #1191331) | Monitorul de evaluare | Cod sursa (job #2387) | Cod sursa (job #3283868)
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
#define NMAX 120001
struct point{
double x, y;
friend bool operator<(const point & p1, const point & p2){
//if (p1.x==p2.x)return p1.y<p2.y;
return p1.x<p2.x;
}
} a[NMAX];
int n;
bool used[NMAX];
vector<int> st;
double cp(point p1, point p2, point p3){
auto r=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
//cout<<"resp: "<<r<<endl;
return r;
}
void conv(){
st.push_back(1),
st.push_back(2);
used[2]=true;
int p=1;
for (int i=3; i>0; i+=(p=(i==n?-p:p))){
if (used[i])continue;
while (st.size()>=2 && cp(a[st[st.size()-1]], a[st[st.size()-2]], a[i])<0.0){
used[st.back()]=false;
//cout<<"in\n";
st.pop_back();
}
//cout<<"out\n\n\n";
st.push_back(i);
used[i]=true;
}
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin>>n;
for (int i=1; i<=n; ++i){
cin>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1);
conv();
st.pop_back();
cout<<st.size()<<endl;
cout<<setprecision(6)<<fixed;
for (auto it:st){
cout<<a[it].x<<" "<<a[it].y<<"\n";
}
return 0;
}