Pagini recente » Cod sursa (job #944325) | Cod sursa (job #489193) | Cod sursa (job #228282) | Cod sursa (job #870206) | Cod sursa (job #2835592)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int dim=200000;
struct pt{
long double x,y;
int ind;
}v[dim];
bool cmp1(pt a,pt b){
if(a.x==b.x){
return a.y<b.y;
}
return a.x<b.x;
}
bool cmp2(pt a,pt b){
if(a.x==b.x){
return a.y>b.y;
}
return a.x<b.x;
}
int ap[dim];
vector<pt>e;
int n,stiva[dim],vf;
long double determinat(pt A,pt B,pt C){
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
bool ccw(pt A,pt B,pt C){
return determinat(A,B,C)>0;
}
void solve(){
sort(e.begin(),e.end(),cmp1);
vf=0;
for(auto it:e){
long double y=it.y;
int ind=it.ind;
while(vf>=2 && !ccw(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
ap[stiva[vf]]--;
vf--;
}
stiva[++vf]=ind;
ap[ind]++;
}
sort(e.begin(),e.end(),cmp2);
vf=0;
for(auto it:e){
long double y=it.y;
int ind=it.ind;
while(vf>=2 && ccw(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
ap[stiva[vf]]--;
vf--;
}
stiva[++vf]=ind;
ap[ind]++;
}
}
signed main(){
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
e.push_back({v[i].x,v[i].y,i});
}
solve();
int nr=0;
for(int i=1;i<=n;i++){
if(ap[i]){
nr++;
}
}
fout<<nr<<'\n';
for(int i=1;i<=n;i++){
if(ap[i]){
fout<<fixed<<setprecision(6)<<v[i].x<<' '<<v[i].y<<'\n';
}
}
}