Cod sursa(job #2955883)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 18 decembrie 2022 00:58:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int MAXN = 120000;
const int INF = 10e8;

struct point{
  double x, y;
};

point points[MAXN];
int noPoints;
vector<point> polygon;

int getStartPoint(){
  int i, index;
  index = 0;
  for( i = 0; i < noPoints; i++ ){
    if( points[index].y > points[i].y )
        index = i;
      else if( points[index].y == points[i].y && points[index].x > points[i].x )
        index = i;
  }

  return index;
}

double getOrientation( point a, point b, point c ){
  return ( b.y - a.y ) * ( c.x - b.x ) - ( c.y - b.y ) * ( b.x - a.x );
}

bool cmp( point a, point b ){
  return getOrientation(points[0], a, b) < 0;
}

void getPolygon(){
  int i;
  polygon.push_back(points[0]);
  polygon.push_back(points[1]);

  for( i = 2; i < noPoints; i++ ){
    while( polygon.size() >= 2 && getOrientation( polygon[polygon.size() - 2], polygon[polygon.size() - 1], points[i] ) >= 0 )
      polygon.pop_back();
    polygon.push_back(points[i]);
  }
}

int main()
{
    int i;
    in>>noPoints;
    for( i = 0; i < noPoints; i++ ){
      in>>points[i].x>>points[i].y;
      //out<<points[i].x<<" "<<points[i].y<<'\n';
    }

    //out<<getStartPoint()<<'\n';
    swap(points[getStartPoint()], points[0]);

    sort(points + 1, points + noPoints, cmp);
    getPolygon();

    out<<polygon.size()<<'\n';
    for( i = 0; i < polygon.size(); i++ ){
      out<<fixed<<setprecision(6)<<polygon[i].x<<" "<<polygon[i].y<<'\n';
    }
    return 0;
}