Pagini recente » Cod sursa (job #813750) | Borderou de evaluare (job #277558) | Cod sursa (job #1059924)
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <iostream>
#define dmax 120000
#define inf 1000000006
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {
double x,y;
/*
bool operator<(point a)
{
return polar() > polar(a);
}*/
};
vector <point> v(120000);
vector <point> hull;
point a,b;
int n;
double s;
//functions declaration
void read();
//reads the input file
double area(point x1, point x2, point x3);
// calculates the area of the triangle formed by the two points x1 & x2 with the origin O(0,0)
void first();
// replaces the first element form the vectorwith the first element from the left;
bool compare(point p1, point p2);
// compares the two polar angles
double polar(point p1);
// returnes the polar angle of the point p1
void write();
//END of declarations
int main() {
read();
first();
for(int i=0;i<n;i++)
cout<<polar(v[i])<<'\n';
a=v[0];
// sort them by the polar angle
sort(v.begin()+1, v.begin()+n, compare);
//browsing the vector and verifying the points
hull.push_back(a);
hull.push_back(v[1]);
for(int i=2; i<n; i++) {
//verific daca elem curent e in poligon sau nu, daca e il bag in coada
if(area(a,hull[hull.size()-1],v[i])>0){
hull[hull.size()-1]=v[i];
}
else
if(area(a,hull[hull.size()-1],v[i])<0){
a=hull[hull.size()-1];
hull.push_back(v[i]);
}
//daca nu e ok il strg pe ultimul si il pun pe asta nou
}
//hull.push_back(v[n-1]);
write();
return 0;
}
void read() {
fin>>n;
for(int i=0; i<n; i++)
fin>>v[i].x>>v[i].y;
}
double area(point p1, point p2, point p3) {
return (p1.x*p2.y+p1.y*p3.x+p2.x*p3.y-p2.x*p1.y-p1.x*p3.y-p3.x*p2.y)/2;
}
bool compare(point p1, point p2) {
//cout<<p2.x<<' '<<p2.y<<';'<<polar(p1)<<' '<<polar(p2)<<'\n';
//if(polar(p1)!=polar(p2))
return (polar(p1)>polar(p2));
//else return (p1.y>p2.y);
}
void first() {
point d;
d.x=inf;
d.y=-inf;
int poz=0;
for(int i=0; i<n; i++) {
if(v[i].x<d.x) {
d=v[i];
poz=i;
}
else if(v[i].x==d.x) if(v[i].y>d.y) {
d=v[i];
poz=i;
}
}
v[poz]=v[0];
v[0]=d;
}
double polar(point x1) {
point p1;
p1.x=x1.x-a.x;
p1.y=x1.y-a.y;
return p1.y/(sqrt(p1.y*p1.y+p1.x*p1.x));
}
void write() {
fout<<hull.size()<<'\n';
for(int i=0; i<hull.size(); i++)
fout<<fixed<<setprecision(12)<<hull[i].x<<' '<<hull[i].y<<'\n';
// cout<<"END SEQ"<<'\n';
}