Pagini recente » Cod sursa (job #1398965) | Cod sursa (job #1932769) | Cod sursa (job #508890) | Cod sursa (job #2647174) | Cod sursa (job #2935444)
#include <bits/stdc++.h>
#define NMAX 120001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
enum Orientare
{
CLOCKWISE,
COUNTERCW,
COLINIARE
};
struct Point
{
long double x, y;
}p[NMAX];
Orientare orientare(Point A, Point B, Point C)
{
long double det=(A.y-B.y)*(C.x-B.x)-(A.x-B.x)*(C.y -B.y);
if(det<0) return CLOCKWISE;
if(det>0) return COUNTERCW;
return COLINIARE;
}
bool comp(Point Pi, Point Pj)
{
if(orientare(p[0], Pi, Pj)==CLOCKWISE) return 0;
if(orientare(p[0], Pi, Pj)==COLINIARE)
{
if(Pi.x>Pj.x) return 0;
if(Pi.x==Pj.x && abs(p[0].y-Pi.y)>abs(p[0].y-Pj.y)) return 0;
}
return 1;
}
vector <Point> v;
void poligon()
{
v.push_back(p[0]);
v.push_back(p[1]);
for(int i=2; i<n; i++)
{
int s=v.size()-1;
while(s>1 && orientare(v[s-1], v[s], p[i])==CLOCKWISE)
{
v.pop_back();
s--;
}
v.push_back(p[i]);
}
}
int main()
{
fin>>n;
for(int i=0; i<n; i++)
{
fin>>p[i].x>>p[i].y;
if(p[0].x>p[i].x)
{
swap(p[0], p[i]);
}
else if(p[0].x==p[i].x)
{
if(p[0].y>p[i].y) swap(p[0], p[i]);
}
}
cout<<p[0].x<<" "<<p[0].y;
sort(p+1, p+n, comp);
//for(int i=0; i<n; i++) fout<<p[i].x<<" "<<p[i].y<<'\n';
poligon();
fout<<v.size()<<'\n';
for(auto & i:v)
{
fout<<fixed<<setprecision(6)<<i.x<<" ";
fout<<fixed<<setprecision(6)<<i.y<<'\n';
}
}