Pagini recente » Cod sursa (job #1426207) | Cod sursa (job #809661) | Cod sursa (job #1733310) | Cod sursa (job #1197837) | Cod sursa (job #2537626)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 120000;
struct punct
{
float x,y;
};
int N;
punct Puncte[NMAX],Stiva[NMAX];
int Contor;
int cnt= 0;
stack < int > S;
void read()
{
f >> N;
for(int i = 1; i <= N; i++)
f >> Puncte[i].x >> Puncte[i].y;
}
void interschimbare(punct a, punct b){
punct t = a;
a = b;
b= t;
}
void sortare()
{
for(int i = 1; i <= N; i++)
{
for(int j = i+1; j<=N; j++)
{
if(Puncte[i].y > Puncte[j].y)
interschimbare(Puncte[i],Puncte[j]);
else if(Puncte[i].y == Puncte[j].y)
if(Puncte[i].x > Puncte[j].x)
interschimbare(Puncte[i],Puncte[j]);
}
}
}
int orientare(punct a,punct b,punct c){
double 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 ConvexHull()
{
S.push(1);
int a = 1;
S.push(2);
int b = 2;
int c;
cnt = 3;
while(cnt <= N)
{
c = cnt;
while(orientare(Puncte[a],Puncte[b],Puncte[c]) < 0){
S.pop();
S.push(c);
b = c;
cnt++;
c = cnt;
}
if(orientare(Puncte[a],Puncte[b],Puncte[c]) >= 0){
S.push(c);
b = c;
cnt++;
c = cnt;
}
}
}
int main()
{
read();
sortare();
ConvexHull();
while(!S.empty()){
cout << S.top() << " ";
S.pop();
}
return 0;
}