Pagini recente » Cod sursa (job #960763) | Cod sursa (job #500691) | Cod sursa (job #528007) | Cod sursa (job #2349400) | Cod sursa (job #2538026)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ifstream 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";
for(int i = 1; i <= cnt;i++)
g << S1[i] << " ";
return 0;
}