#include <iostream> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <queue> #include <iomanip> #include <math.h> using namespace std; struct point { long double x,y; int num; point (double a,double B)/>{x = a; y = b;} point (){x = 0; y = 0;} point operator+(const point p){ point z(0,0); z.x = x + p.x; z.y = y + p.y; return z;} point operator-(const point p){ point z(0,0); z.x = x - p.x; z.y = y - p.y; return z;} double operator*(const point p){ return sqrt((p.x-x)*(p.x-x) + (p.y-y)*(p.y-y));} }; point x[500000],ma(10000000000,0),mb(-10000000000,0); vector <point > ans,a,b,s;int n; long double sqr(point x1,point x2,point x3) { return (x2.x - x1.x)*(x3.y - x1.y ) - (x2.y - x1.y)*(x3.x - x1.x); } bool comp(point a,point B)/> { return (a.x < b.x || (a.x == b.x && a.y < b.y)); } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); freopen("hullp.in","r",stdin); freopen("hullp.out","w",stdout); cin >> n; for(int i(0);i<n;i++) { cin >> x[i].x >> x[i].y; x[i].num = i; if(x[i].x < ma.x || (x[i].x == ma.x && ma.y > x[i].y)) ma = x[i]; if(x[i].x > mb.x || (x[i].x == mb.x && mb.y < x[i].y)) mb = x[i]; } for(int i(0);i<n;i++) { if(i == ma.num || i == mb.num) continue; if(sqr(ma,mb,x[i]) == 0) continue; if(sqr(ma,mb,x[i]) < 0) a.push_back(x[i]); else b.push_back(x[i]); } a.push_back(ma);b.push_back(ma); a.push_back(mb);b.push_back(mb); sort(a.begin(),a.end(),comp); sort(b.begin(),b.end(),comp); ans.push_back(b[0]);ans.push_back(b[1]); for(int i(2);i<b.size();i++) { int z = ans.size(); double g = sqr(ans[z-2],ans[z-1],b[i]); while(ans.size() > 1 && sqr(ans[ans.size()-2],ans[ans.size()-1],b[i]) >= 0) ans.pop_back(); ans.push_back(b[i]); } s.push_back(a[0]);s.push_back(a[1]); for(int i(2);i<a.size();i++) { while(s.size() > 1 && sqr(s[s.size()-2],s[s.size()-1],a[i])<= 0) s.pop_back(); s.push_back(a[i]); } for(int i(s.size()-2);i>0;i--) ans.push_back(s[i]); }
- Публикации yanush
Публикации yanush
2 публикаций создано yanush (учитываются публикации только с 12-мая 23)
По типу контента
По пользователю
Сортировать
Порядок
#375 Выпуклая оболочка Грэхэм
Отправлено от yanush в 04 февраля 2015 - 17:15 in Геометрия
#374 Пересечение двух отрезков
Отправлено от yanush в 31 января 2015 - 14:28 in Геометрия
struct point{ double x; double y; }; struct vec{ double x; double y; }; bool perlo(point x1, point x2, point x3, point x4){ const double INF = 1000000000000; bool ans = false; vec q,p; q.x = x1.x-x2.x; q.y = x1.y-x2.y; p.x = x3.x-x4.x; p.y = x3.y-x4.y; double x = 0; double y = 0; double r = 0; double b = (x3.y*q.x-x1.y*q.x-x3.x*q.y+x1.x*q.y) / (p.x*q.y-p.y*q.x); if(p.x*q.y-p.y*q.x == 0){ r = abs((x1.x-x3.x)*p.y - (x1.y-x3.y)*p.x); if( r<0.000000001 ){ x = INF; }else{ x = -INF; } } if(p.x*q.y-p.y*q.x != 0){ x = x3.x+p.x*b; y = x3.y+p.y*b; } if(x == INF){ if( (((x1.x <= x3.x && x1.x >= x4.x) || (x1.x >= x3.x && x1.x <= x4.x)) &&((x1.y <= x3.y && x1.y >= x4.y) || (x1.y >= x3.y && x1.y <= x4.y))) || (((x2.x <= x3.x && x2.x >= x4.x) || (x2.x >= x3.x && x2.x <= x4.x)) &&((x2.y <= x3.y && x2.y >= x4.y) || (x2.y >= x3.y && x2.y <= x4.y))) ) ans = true; } if( (((x <= x1.x && x >= x2.x) || ( x >= x1.x && x <= x2.x)) &&((y <= x1.y && y >= x2.y) || ( y >= x1.y && y <= x2.y))) && (((x <= x3.x && x >= x4.x) || ( x >= x3.x && x <= x4.x)) &&((y <= x3.y && y >= x4.y) || ( y >= x3.y && y <= x4.y))) ) ans = true; //cout <<x <<endl <<y<<endl; return ans; // (x,y) - точка пересечения прямых. // ans - имеют ли отрезки общие точки }
- → Публикации yanush