Mai intai trebuie sa te autentifici.
Cod sursa(job #933521)
| Utilizator | Data | 30 martie 2013 01:12:11 | |
|---|---|---|---|
| Problema | Infasuratoare convexa | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.05 kb |
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 120005
#define x second
#define y first
#define TYPE pair <double,double>
#define L s.size()
using namespace std;
int n;
vector<int> s;
TYPE v[NMAX];
void read()
{
ifstream fin("infasuratoare.in");
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
fin.close();
}
void print()
{
ofstream fout("infasuratoare.out");
fout<<L<<'\n';
for(int i=L;i;i--)
fout<<fixed<<v[s[i-1]].x<<' '<<v[s[i-1]].y<<'\n';
fout.close();
}
inline double area(TYPE a,TYPE b,TYPE c)
{
return a.x * b.y + b.x * c.y + c.x * a.y -
b.x * a.y - c.x * b.y - a.x * c.y;
}
inline bool cmp(TYPE a,TYPE b)
{
return (area(v[1],a,b)<0);
}
void solve()
{
int poz=1;
for(int i=2;i<=n;i++)
if(v[i]<v[poz])
poz=i;
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
s.push_back(1);
s.push_back(2);
for(int i=3;i<=n;i++)
{
while(L>=1 && area(v[s[L-2]],v[s[L-1]],v[i])>0)
s.pop_back();
s.push_back(i);
}
}
int main()
{
read();
solve();
print();
return 0;
}
