Pagini recente » Cod sursa (job #2613921) | Cod sursa (job #1194657) | Cod sursa (job #242660) | Cod sursa (job #179605) | Cod sursa (job #2128038)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <iomanip>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NLIM = 12e4 + 10;
struct pont
{
ld x, y;
};
int n;
pont vp[NLIM];
ld dist2(pont p1, pont p2)
{
return (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
}
int orientation(pont p1, pont p2, pont p3)
{
ld val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
if(val < 0)
return -1;///left
if(val > 0)
return 1;///right
return 0;///collinear
}
int compare(const void* a, const void* b)
{
pont p1 = *(pont*)a;
pont p2 = *(pont*)b;
int ori = orientation(vp[0], p1, p2);
if(!ori)
return dist2(vp[0], p1) - dist2(vp[0], p2);
return ori;
}
int main()
{
int st = 0;
fin >> n;
for(int i = 0; i < n; ++i)
{
fin >> vp[i].x >> vp[i].y;
if(vp[i].x < vp[st].x || (vp[i].x == vp[st].x && vp[i].y < vp[st].y))
st = i;
}
pont emp = vp[st];
vp[st] = vp[0];
vp[0] = emp;
qsort(vp + 1, n-1, sizeof(pont), compare);
stack <int> conv;
conv.push(0);
conv.push(1);
for(int i = 2; i < n; ++i)
{
bool b = true;
while(b)
{
b = false;
int i2 = conv.top();
conv.pop();
int i1 = conv.top();
int ori = orientation(vp[i1], vp[i2], vp[i]);
if(ori <= 0)
{
conv.push(i2);
}
else
{
b = true;
}
}
conv.push(i);
}
fout << conv.size() << "\n";
stack <int> revconv;
while(conv.size())
{
revconv.push(conv.top());
conv.pop();
}
while(revconv.size())
{
int cur = revconv.top();
fout << fixed << setprecision(6) << vp[cur].x << " " << vp[cur].y << "\n";
revconv.pop();
}
return 0;
}