Pagini recente » Cod sursa (job #1841462) | Cod sursa (job #699772) | Monitorul de evaluare | Cod sursa (job #619929) | Cod sursa (job #3265357)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream d("infasuratoare.out");
struct coordonate{
double x = 2000;
double y = 2000;
int i;
};
int n, x, y;
coordonate ppunct, coord[101], rez[101];
vector <int> v;
double det(double p1x, double p1y, double p2x, double p2y, double p3x, double p3y)
{
return (p1x*p2y)+(p3x*p1y)+(p2x*p3y)-(p2y*p3x)-(p1y*p2x)-(p1x*p3y);
}
bool sortare_det(coordonate coordA, coordonate coordB)
{
int detA;
detA = det(ppunct.x, ppunct.y, coordA.x, coordA.y, coordB.x, coordB.y);
if(detA > 0) return 1;
else return 0;
}
int main()
{
f>>n;
for(int i = 1; i<=n; i++)
{
f>>coord[i].x>>coord[i].y;
if(coord[i].x <= ppunct.x && coord[i].y <= ppunct.y)
{
ppunct.x = coord[i].x;
ppunct.y = coord[i].y;
ppunct.i = i;
}
}
swap(coord[ppunct.i], coord[1]);
sort(coord+2, coord+n+1, sortare_det);
v.push_back(1);
v.push_back(2);
for(int i = 3; i<=n; i++)
{
int x = v.size();
int c1 = v[x-2], c2 = v[x-1];
double detA;
detA = det(coord[c1].x, coord[c1].y, coord[c2].x, coord[c2].y, coord[i].x, coord[i].y);
while(v.size() > 1 && detA < 0)
{
v.pop_back();
x--;
if(v.size() <= 1) break;
c1 = v[x-2], c2 = v[x-1];
detA = det(coord[c1].x, coord[c1].y, coord[c2].x, coord[c2].y, coord[i].x, coord[i].y);
}
v.push_back(i);
}
d<<v.size()<<'\n';
for(auto x:v)
{
d<<fixed << setprecision(6) << coord[x].x<<' '<<coord[x].y<<'\n';
}
}