Перейти к содержимому


Публикации yanush

2 публикаций создано yanush (учитываются публикации только с 29-марта 23)


#375 Выпуклая оболочка Грэхэм

Отправлено от yanush в 04 февраля 2015 - 17:15 in Геометрия

#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]);
}



#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 - имеют ли отрезки общие точки
}