Pagini recente » Cod sursa (job #2580185) | Cod sursa (job #2207934) | Cod sursa (job #1987133) | Cod sursa (job #1317519) | Cod sursa (job #2067368)
#include <fstream>
#include <deque>
#include <iomanip>
#include <vector>
#include <algorithm>
#define DIM 120002
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
vector<int> sol;
int n, nr, viz[DIM];
double xmin, ymin;
deque<int> c;
struct punct{
double x, y;
}pct[DIM];
double arie(punct a, punct b){
return a.x * b.y - a.y * b.x;
}
double dist(punct a){
return a.x * a.x + a.y * a.y;
}
bool cmp(punct a, punct b){
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double det(punct a, punct b, punct c){
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
int main()
{
f>>n;
for(int i = 1; i <= n; ++ i){
f>>pct[i].x>>pct[i].y;
if(pct[i].x < xmin){
xmin = pct[i].x;
}
if(pct[i].y < ymin){
ymin = pct[i].y;
}
}
for(int i = 1; i <= n; ++ i){
pct[i].x += xmin;
pct[i].y += ymin;
}
sort(pct + 1, pct + n + 1, cmp);
c.push_back(1);
c.push_back(2);
//c.push_back(3);
for(int i = 3; i <= n; ++ i){
punct A, B, C;
while(c.size() >= 2){
A = pct[c[c.size() - 2]];
B = pct[c[c.size() - 1]];
C = pct[i];
if(det(A, B, C) <= 0){
c.pop_back();
}
else
break;
}
c.push_back(i);
}
for(int i = 0; i < c.size(); ++ i)
sol.push_back(c[i]);
c.clear();
c.push_back(n);
c.push_back(n - 1);
for(int i = n - 2; i >= 1; -- i){
punct A, B, C;
while(c.size() >= 2){
A = pct[c[c.size() - 2]];
B = pct[c[c.size() - 1]];
C = pct[i];
if(det(A, B, C) <= 0)
c.pop_back();
else
break;
}
c.push_back(i);
}
for(int i = 1; i < c.size() - 1; ++ i)
sol.push_back(c[i]);
g<<sol.size()<<'\n';
for(int i = 0; i < sol.size(); ++ i){
g<<setprecision(10)<<fixed<<pct[sol[i]].x - xmin<<" ";
g<<setprecision(10)<<fixed<<pct[sol[i]].y - ymin<<'\n';
}
return 0;
}