Cod sursa(job #1989860)

Utilizator MotoAMotoi Alexandru MotoA Data 9 iunie 2017 12:12:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct{
 double x,y;
};
Punct p[120001];
vector <Punct> st;
int n,nr;
double det(Punct A, Punct B, Punct C){
 return (A.x-B.x)*(B.y-C.y)-(A.y-B.y)*(B.x-C.x);
}
bool compd(Punct a,Punct b){
 return det(p[1],a,b)<0;
}
bool compx(Punct a,Punct b){
 if(a.x==b.x)return a.y<b.y;
 return a.x<b.x;
}
void citire(){
int minx=1;
f>>n;
for(int i=1;i<=n;i++){
    f>>p[i].x>>p[i].y;
  if(compx(p[i],p[minx]))
    minx=i;
}
swap(p[minx],p[1]);
}
void Graham(){
sort(p+2,p+n+1,compd);
 st.reserve(n+1);
 st.push_back(p[1]);
 st.push_back(p[2]);
 for(int i=3;i<=n;i++){
  while(st.size()>=2 && det(st[st.size()-2],st[st.size()-1],p[i])>0)
    st.pop_back();
  st.push_back(p[i]);
 }
}

void afisare(){
 g<< st.size()<<'\n';
 g<<fixed<<setprecision(6);
for(vector<Punct>::reverse_iterator it=st.rbegin();it!=st.rend();++it)
 g<< (*it).x<<' '<<(*it).y<<'\n';
}
int main(){
citire();
Graham();
afisare();
return 0;
}