Pagini recente » Istoria paginii runda/28-03-2017_todo | Cod sursa (job #245219) | Cod sursa (job #2943051) | Cod sursa (job #1007103) | Cod sursa (job #1996658)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int const nmax = 120000;
struct Point {
double x;
double y;
bool operator < (Point a) const {
//pe varena vei face tot asa, numai ca functia va fi usor diferita
return y < a.y;
}
};
Point v[1 + nmax];
//|a.x a.y 1|a.x a.y 1
//|b.x b.y 1|b.x b.y 1
//|c.x c.y 1|c.x c.y 1
double det3(Point a, Point b, Point c) {
double plus = a.x * b.y + a.y * c.x + a.x * b.y;
double minus = b.y * c.x + a.y * b.x + a.x * c.y;
return (plus - minus);
}
bool compare(Point a, Point b){
return (0 < det3(v[1] , a , b));
}
vector <int> st;
int main() {
int n;
in >> n;
int imin = 1;
for(int i = 1 ; i <= n; i++){
in >> v[i].x >> v[i].y;
if(v[i] < v[imin]){
imin = i;
}
}
swap(v[1] , v[imin]);
sort(v + 2 , v + n + 1 , compare);
st.push_back(1);
st.push_back(2);
st.push_back(3);
for(int i = 4 ; i <= n ;i++){
while(det3(v[st[st.size() - 2]], v[st[st.size() - 1]], v[i]) < 0){
st.pop_back();
}
st.push_back(i);
}
out<<st.size()<<'\n';
out<<setprecision(6)<<fixed;
for(int i = 0 ; i < st.size() ;i++){
out<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
}
return 0;
}