Pagini recente » Cod sursa (job #1487810) | Cod sursa (job #2538028)
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 120000;
struct Point{
float x,y;} X[NMAX];
int N;
int S1[NMAX],cnt;
int S2[NMAX],cnt2;
bool in[NMAX];
void read(){
f >> N;
for(int i = 1; i <= N;i++)
f >> X[i].x >> X[i].y;
}
int Orientare(Point a, Point b, Point c){
int rez = (a.x*b.y) + (b.x*c.y) +(c.x*a.y) - (b.y*c.x) - (c.y*a.x) - (a.y*b.x);
if (rez <0) return -1;
if(rez>0) return 1;
return 0;
}
void swapp(Point &a, Point &b){
Point t = a;
a = b;
b = t;
}
void Sort(){
for(int i = 1; i <= N;i++)
for(int j = i+ 1; j <= N;j++){
if(X[i].y > X[j].y)
swapp(X[i],X[j]);
else if(X[i].y == X[j].y)
if(X[i].x > X[j].x)
swapp(X[i],X[j]);
}
}
void ConvexHull(){
S1[1] = 1;
in[S1[1]] = true;
S1[2] = 2;
in[S1[2]] = true;
cnt = 2;
for(int i = 3; i <= N;i++){
while(Orientare(X[S1[cnt]],X[S1[cnt-1]],X[i]) > 0){
in[S1[cnt]] = false;
cnt--;
}
S1[++cnt] = i;
in[S1[cnt]] = true;
}
S2[1] = 1;
S2[2] = 2;
cnt2 = 2;
for(int i = 3; i <= N;i++){
while(Orientare(X[S2[cnt2]], X[S2[cnt2-1]], X[i]) < 0 )
cnt2--;
S2[++cnt2] = i;
}
}
void Legare(){
for(int i = cnt2; i >= 1;i--){
if(!in[S2[i]])
S1[++cnt] = S2[i];
}
}
int main()
{
read();
Sort();
ConvexHull();
Legare();
g << cnt << "\n";
g << fixed << showpoint << setprecision(6);
for(int i = 1; i <= cnt;i++)
g << setprecision(6) << X[S1[i]].x << " " << setprecision(6) << X[S1[i]].y << "\n";
return 0;
}