Nu aveti permisiuni pentru a descarca fisierul DesertFountain.jpg
Cod sursa(job #3214394)
Utilizator | Data | 14 martie 2024 09:04:01 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.65 kb |
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
};
enum Orientare
{
trigonometric,
antitrigonometric,
};
Orientare calcOrientare(punct p1, punct p2, punct p3)
{
double det=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
if(det>0)
{
return trigonometric;
}
if(det<0)
{
return antitrigonometric;
}
}
int main()
{
punct a[101];
fout<<setprecision(6)<<fixed;
int n;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1, [](punct a, punct b)
{
if(a.x>b.x || a.x==b.x && a.y>b.y)
{
return false;
}
return true;
});
vector<int> sol, sol2;
sol.push_back(1);
sol.push_back(2);
for(int i=3; i<=n; i++)
{
while(calcOrientare(a[sol[sol.size()-2]], a[sol[sol.size()-1]], a[i])==trigonometric)
{
sol.pop_back();
}
sol.push_back(i);
}
sol2.push_back(n);
sol2.push_back(n-1);
for(int i=n-2; i>=1; i--)
{
while(calcOrientare(a[sol2[sol2.size()-2]], a[sol2[sol2.size()-1]], a[i])==trigonometric)
{
sol2.pop_back();
}
sol2.push_back(i);
}
for(int i=0; i<sol.size(); i++)
{
fout<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
}
for(int i=1; i<sol2.size()-1; i++)
{
fout<<a[sol2[i]].x<<" "<<a[sol2[i]].y<<"\n";
}
return 0;
}