Pagini recente » Cod sursa (job #278550) | Cod sursa (job #1829518) | Cod sursa (job #1545929) | Cod sursa (job #2740933) | Cod sursa (job #1086751)
#include<iostream>
#include<fstream>
#include<vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX_N = 120001;
int n;
double x[MAX_N], y[MAX_N];
double min_x, min_y;
void read(){
fin >> n;
fin >> x[1] >> y[1];
min_x = x[1];
min_y = y[1];
for(int i=2; i<=n; i++){
fin >> x[i] >> y[i];
if(x[i] < min_x){
min_x = x[i];
min_y = y[i];
}else if(x[i] == min_x){
if(y[i] < min_y){
min_y = y[i];
}
}
}
}
struct Point{
double x, y;
double tg;
};
vector<Point> list;// lista in care ordonez punctele in functie de tangenta cu punctul de coordonate (min_X, min_y)
#define pb push_back
void addToList(Point p, int li, int ls){
if(list.size() == 0){
list.pb(p);
}else if(ls - li == 0){
int lm = (li+ls)/2;
if(list[lm].tg > p.tg){
list.insert(list.begin() + lm , p);
}else list.insert(list.begin()+lm+1, p);
}else {
int lm = (li+ls)/2;
if(list[lm].tg < p.tg) addToList(p, lm+1, ls);
else addToList(p, li, lm);
}
}
void sort(){
for(int i=1; i<=n; i++){
if(x[i] != min_x || y[i] != min_y){
Point p;
p.x = x[i];
p.y = y[i];
p.tg = (p.y - min_y)/(p.x - min_x);
addToList(p,0, list.size()-1);
}
}
}
vector<Point> st;
void solve(){
Point p;
p.x = min_x;
p.y = min_y;
st.push_back(p);
st.push_back(list[0]);
// (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
for(size_t i=1; i<list.size(); i++){
size_t lung = st.size()-1;
double x1 = st[lung-1].x;
double y1 = st[lung-1].y;
double x2 = st[lung].x;
double y2 = st[lung].y;
double x3 = list[i].x;
double y3 = list[i].y;
double res = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
if(res > 0) st.push_back(list[i]);
else{
st.pop_back();
st.push_back(list[i]);
}
}
fout << st.size() << '\n';
fout.setf( std::ios::fixed, std:: ios::floatfield );
fout.precision(12);
for(size_t i=1; i<st.size(); i++){
fout << st[i].x << " " << st[i].y << '\n';
}
fout << st[0].x << " " << st[0].y << '\n';
}
int main(){
read();
sort();
solve();
return 0;
}