Pagini recente » Cod sursa (job #566567) | Cod sursa (job #1133878) | Cod sursa (job #767508) | Cod sursa (job #481392) | Cod sursa (job #1533689)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <utility>//pair
#include <algorithm>
#include <assert.h>
#define Inf (1<<31)-1
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<pair<float,float> > v;
vector< pair<pair<float,float>, float> > nv;
pair<float,float> mini;
stack<int> S;
int n;
float abs(float x)
{
return (x<0? -x: x);
}
float cos(pair<float,float> a)
{
float x,y;
x=(a.first - mini.first);
y=(a.second - mini.second);
if(x==0) {
if (y == 0)
return -0.00000000000000001;
else
return Inf;
}
return y/x;
}
int cmp(pair<float,float> a, pair<float,float> b) {
float cos1,cos2;
cos1=cos(a);
cos2=cos(b);
if(cos1>=0 && cos2>0)
return cos1>cos2;
else if(cos1<0 && cos2<0)
return cos1>cos2;
return cos1<0 && cos2>0;
}
void citire()
{
int i;
float d1,d2;//
fin>>n;
mini.second=1000000000;//
for(i=1; i<=n; i++)
{
fin>>d1>>d2;//depanarea nu trece de citire
if(d2<mini.second)
mini=make_pair(d1,d2);
v.push_back(make_pair(d1,d2));
}
}
int left_turn(pair<float, float> p1, pair<float, float> p2, pair<float, float> 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);
//assert (leftTurn (make_pair (1, 1), make_pair (2, 2), 3) == 1);
S.push(0);
for(int i=1; i<n; i++)
{
int emij=S.top();
S.pop();
while(S.size() && left_turn(v[S.top()],v[emij],v[i])>0){//>0
emij=S.top();
S.pop ();
}
S.push(emij);
S.push (i);
}
int sz = S.size ();
cout<<sz<<'\n';
while(S.size())
{
int emij=S.top();
S.pop ();
printf ("%.2lf %.2lf\n", v[emij].first, v[emij].second);
}
return 0;
}