Pagini recente » algoritmiada-2018/runda-finala/clasament/seniori | Clasament .com | Cod sursa (job #1172876) | Cod sursa (job #131879) | Cod sursa (job #360950)
Cod sursa(job #360950)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
struct punct{
double x;
double y;
};
bool good(punct& p1,punct& p2,punct& p3){
if( ( (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x) )<0) return false;
return true;
}
class comp{
punct referinta;
public:
comp(punct X):referinta(X){}
bool operator()(const punct& p1,const punct& p2){
return ( (p1.x-referinta.x)/(p1.y-referinta.y) > (p2.x-referinta.x)/(p2.y-referinta.y) );
}
};
int main(){
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in>>n;
vector<punct> v(n);
int min=0;
for(int i=0;i<n;i++){
in>>v[i].x>>v[i].y;
if(v[i].y>v[min].y){
min=i;
}
}
vector<punct> s;
s.push_back(v[min]);
comp comparatie(v[min]);
v.erase(v.begin()+min);
sort(v.begin(),v.end(),comparatie);
s.push_back(v[0]);
for(int i=1;i<v.size();i++){
while(!good(s[s.size()-2],s[s.size()-1],v[i])){
s.pop_back();
}
s.push_back(v[i]);
}
out<<s.size()<<endl;
int primu=0;
for(int i=0;i<s.size();i++){
if(s[i].y/s[i].x<s[primu].y/s[primu].x) primu=i;
}
for(int i=primu;i<s.size();i++){
out<<s[i].x<<" "<<s[i].y<<endl;
}
for(int i=0;i<primu;i++){
out<<s[i].x<<" "<<s[i].y<<endl;
}
}