Pagini recente » Cod sursa (job #2159486) | Cod sursa (job #292363) | Cod sursa (job #424323) | Cod sursa (job #3236188) | Cod sursa (job #1091933)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX_N = 120001;
int n, index=0;
double min_x, min_y;
struct Point{
double x, y;
double tg;
}p[MAX_N];
void read(){
fin >> n;
fin >> p[1].x >> p[1].y;
min_x = p[1].x;
min_y = p[1].y;
index = 1;
for(int i=2; i<=n; i++){
fin >> p[i].x >> p[i].y;
if(p[i].x < min_x){
min_x = p[i].x;
min_y = p[i].y;
index = i;
}else if(p[i].x == min_x){
if(p[i].y < min_y){
min_y = p[i].y;
index = i;
}
}
}
}
vector<Point> list;// lista in care ordonez punctele in functie de tangenta cu punctul de coordonate (min_X, min_y)
bool cmp(Point p1, Point p2){
p1.tg = (p1.y - min_y)/(p1.x - min_x);
p2.tg = (p2.y - min_y)/(p2.x - min_x);
return p1.tg < p2.tg;
}
#define pb push_back
vector<Point> st;
void solve(){
swap(p[index],p[1]);
sort(p+2,p+n+1,cmp);
st.push_back(p[1]);
st.push_back(p[2]);
// (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
for(int i=3; i<n+1; 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 = p[i].x;
double y3 = p[i].y;
double res = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
if(res > 0) st.push_back(p[i]);
else{
st.pop_back();
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();
solve();
return 0;
}