Pagini recente » Cod sursa (job #1966282) | Cod sursa (job #2419017) | Cod sursa (job #760583) | Cod sursa (job #583720) | Cod sursa (job #1361901)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> // std::sort
#define inf 0x7fffffff
using namespace std;
struct nod
{
double x,y;
double m;
void atr(double a, double b)
{
x=a;
y=b;
}
}st;
int n;
vector<nod>v;
void citire()
{
st.atr(inf,inf);
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
double a,b;
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&a,&b);
nod aux;
aux.atr(a,b);
v.push_back(aux);
if(b<st.y)
{
st=aux;
swap(v[0],v[v.size()-1]);
}
else
if(b==st.y && a>st.x)
{
st=aux;
swap(v[0],v[v.size()-1]);
}
}
for(int i=1;i<n;i++)
if(v[i].y==st.y)
v[i].m=-inf;
else if(v[i].x==st.x)
v[i].m=0;
else
v[i].m=(v[i].y-st.y)/(v[i].x-st.x);
}
bool cmp(nod a, nod b)
{
if(a.m>0 && b.m>0)
return a.m<b.m;
else if(a.m>0 && b.m<=0)
return true;
else if(a.m==-inf)
return a.m>b.m;
else
if(a.m<0 && b.m<0)
return a.m<b.m;
else
if(a.m==0 && b.m<0)
return true;
}
int semndetneg(nod a, nod b, nod c)
{
if(b.y*(a.x-c.x)+c.y*(b.x-a.x)+a.y*(c.x-b.x)>0)
return 1;
return 0;
}
vector <nod> sol;
void magie()
{
sol.push_back(st);
sol.push_back(v[1]);
for(int i=2;i<n;i++)
{
if(semndetneg(sol[sol.size()-2],sol[sol.size()-1],v[i]))
{
sol.push_back(v[i]);
continue;
}
else
{
sol.erase(sol.begin()+sol.size()-1,sol.begin()+sol.size());
i--;
continue;
}
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++)
printf("%lf %lf\n",sol[i].x,sol[i].y);
}
int main()
{
citire();
sort(v.begin()+1,v.end(),cmp);
magie();
return 0;
}