Pagini recente » Cod sursa (job #774152) | Cod sursa (job #1514584) | Cod sursa (job #1049241) | Cod sursa (job #988997) | Cod sursa (job #1629737)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <utility>//pair
#include <algorithm>
#include <assert.h>
#include <iomanip>
#define Inf (1<<31)-1
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<pair<double,double> > v;
vector< pair<pair<double,double>, double> > nv;
pair<double,double> mini;
int n;
double abs(double x) {
return (x<0? -x: x);
}
double tg(pair<double,double> a) {
double x,y;
x=(a.first - mini.first);
y=(a.second - mini.second);
if(x==0) {
if (y == 0)
return Inf;
else
return Inf-1;
}
return y/x;
}
int cmp(pair<double,double> a, pair<double,double> b) {
double tg1, tg2;
tg1 = tg(a);
tg2 = tg(b);
return tg1 > tg2;
}
void citire() {
int i;
double d1,d2;//
scanf("%d", &n);
mini.second=Inf;//
mini.first=Inf;//
for(i=1; i<=n; i++) {
scanf("%lf %lf", &d1, &d2);
if(d1<mini.first || (d1 == mini.first && d2 < mini.second)) //luam cel mai din stanga punct si face tg adica y/x adica panta.
mini=make_pair(d1,d2);
v.push_back(make_pair(d1,d2));
}
}
int left_turn(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3) {
return (p1.first*p2.second)-(p2.second*p3.first)+(p2.first*p3.second)-(p2.first*p1.second)+(p1.second*p3.first)-(p3.second*p1.first);
}
int main() {
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
citire();
sort(v.begin(),v.end(),cmp);
vector<int> S;
S.push_back(0);
for(int i=1; i<n; i++) {
while(S.size() >= 2 && left_turn(v[ S[S.size()-2] ], v[S.back()], v[i]) > 0)
S.pop_back(); //daca noul nod e mai la stanga
S.push_back(i); //punctul nou
}
int sz = S.size();
cout<<sz<<'\n';
for(int i=0; i<S.size(); ++i) {
//printf ("%.2lf %.2lf\n", v[emij].first, v[emij].second);
cout<<fixed<<setprecision(6)<<v[S[i]].first<<' '<<v[S[i]].second<<'\n';
}
return 0;
}