Cod sursa(job #700056)

Utilizator bacilaBacila Emilian bacila Data 29 februarie 2012 23:12:47
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <fstream>
#include<stack>
using namespace std;
pair<long double,long double> a[120003],m,qq;
int n,i,ok;
stack<pair<long double,long double> > s;
bool cmp(pair<long double,long double> x,pair<long double,long double> y)
{
     if(x.first==m.first)
     return false;
     if(y.first==m.first)
     return true;
     return !(((x.second-m.second)/(x.first-m.first)>(y.second-m.second)/(y.first-m.first))||(((x.second-m.second)/(x.first-m.first)==(y.second-m.second)/(y.first-m.first))&&x.first>y.first));
 
     }
int main ()
{m.first=2000000000;
m.second=2000000000;
ifstream f("infasuratoare.in");
 ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++)
{f>>a[i].first>>a[i].second;
if(a[i].first<m.first||(a[i].first==m.first&&m.second>a[i].second))
{m.first=a[i].first;
m.second=a[i].second;
}
}
for(i=1;i<=n;i++)
if(m.first==a[i].first&&m.second==a[i].second)
break;
for(;i<n;i++)
a[i]=a[i+1];
n--;
qq=m;
sort(a+1,a+n+1,cmp);


s.push(a[1]);
s.push(a[2]);

for(i=3;i<=n;i++)
{ok=1;
while(s.size()>1&&ok)
{m=s.top();
s.pop();
if(s.top().first*m.second+m.first*a[i].second+a[i].first*s.top().second-s.top().first*a[i].second-m.first*s.top().second-a[i].first*m.second>0)                 
{s.push(m);
ok=0;}}
s.push(a[i]);
}n=0;
while(!s.empty())
{a[++n]=s.top();
s.pop();}
a[0]=qq;
g<<n+1<<'\n';
while(n>=0)
{g<<a[n].first<<" "<<a[n].second<<'\n';
n--;}
 f.close(); g.close();
return 0;
}