Pagini recente » Cod sursa (job #1786608) | Cod sursa (job #1419349) | Cod sursa (job #2252210) | Cod sursa (job #2762977) | Cod sursa (job #701886)
Cod sursa(job #701886)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
#define nmax 120005
using namespace std;
int n;
vector<pair<double, double> > pct, st;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool cmp(pair<double,double> a, pair<double,double> b){
if ( (a.x < b.x) || (a.x == b.x && a.y < b.y) )
return true;
else return false;
}
void citeste(){
f >> n;
//citesc punctele
for(int i=1; i<=n; i++){
double x, y;
f >> x >> y;
pct.push_back(make_pair(x,y));
}
//le sortez crescator dupa x si in caz de egalitate dupa y
sort(pct.begin(), pct.end(), cmp );
}
bool verif(pair<double,double> A, pair<double,double> B, pair<double,double> C){
double a = A.y - B.y;//y1 - y2
double b = B.x - A.x;//x2 - x1
double c = A.x*B.y - B.x * A.y;//x1 * y2 - x2 * y1;
double ecu = a * C.x + b * C.y + c;
return (ecu < 0);
}
void rezolva(){
//adaug primele 2 pct
st.push_back(make_pair(pct[0].x, pct[0].y));
st.push_back(make_pair(pct[1].x, pct[1].y));
for(int i=2; i<pct.size(); i++){
while (st.size() > 1 && verif( st[st.size()-2], st[st.size()-1], pct[i] ) )
st.pop_back();
st.push_back(make_pair(pct[i].x, pct[i].y));
}
for(int i=pct.size()-2; i>=0; i--){
while (st.size() > 1 && verif( st[st.size()-2], st[st.size()-1], pct[i] ) )
st.pop_back();
st.push_back(make_pair(pct[i].x, pct[i].y));
}
st.pop_back();
}
void scrie(){
g << st.size() << "\n";
for(int i=0; i<st.size(); i++){
g << fixed;
g << setprecision(12) << st[i].x << " " << setprecision(12) << st[i].y << "\n";
}
}
int main(){
citeste();
rezolva();
scrie();
f.close();
g.close();
return 0;
}