Pagini recente » Cod sursa (job #1821531) | Cod sursa (job #2477285) | Cod sursa (job #1685873) | Cod sursa (job #2150772) | Cod sursa (job #1667731)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <utility>
#define INF ((1<<31)-1)
#define x first
#define y second
using namespace std;
int N;
vector < pair < double, double > > V;
vector < int > S;
pair < double, double > mini;
void citire();
int cmp(const pair<double, double> &a, const pair<double, double> &b);
double tg (const pair<double, double> a);
void infasuratoare();
bool leftTurn(const pair<double, double> &p1, const pair<double, double> &p2, const pair<double, double> &p3);
void afisare();
int main()
{
citire();
sort(V.begin(), V.end(), cmp);
infasuratoare();
afisare();
return 0;
}
void afisare() {
cout<<S.size()<<'\n';
for(int i=S.size()-1; i>=0; --i) {
cout<<fixed<<setprecision(6)<<V[S[i]].x<<' '<<V[S[i]].y<<'\n';
}
}
bool leftTurn(const pair<double, double> &p1, const pair<double, double> &p2, const pair<double, double> &p3) {
return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y) > 0;
}
void infasuratoare()
{
for(int i=0; i<N; ++i) {
while(S.size() > 1 && leftTurn( V[ S[S.size()-2] ], V[ S[S.size()-1] ], V[i] ) )
S.pop_back();
S.push_back(i);
}
}
double tg (const pair<double, double> a) {
double xx, yy;
xx = a.x - mini.x;
yy = a.y - mini.y;
if(xx == 0) {
if(yy == 0)
return INF;
else
return INF-1;
}
return yy/xx;
}
int cmp(const pair<double, double> &a, const pair<double, double> &b) {
return tg(a) > tg(b);
}
void citire()
{
freopen("infasuratoare.in", "rt", stdin);
freopen("infasuratoare.out", "wt", stdout);
scanf("%d", &N);
double a, b;
mini.x = mini.y = INF;
for(int i=1; i<=N; ++i) {
scanf("%lf%lf", &a, &b);
if(a < mini.x || (a == mini.x && b < mini.y) )
mini = make_pair(a, b);
V.push_back( make_pair(a, b) );
}
}