ACM夏休み合宿10

今日は主な学習力で幾何学的基礎を計算します.
以下は主に幾何学を計算するいくつかのアルゴリズムのコードを与えますが、問題を解析するには、必要なアルゴリズムを知ることも重要です.
1.凸包
1)先に凸包を巻くために必要なデータ構造

        ：
struct Point {
	double x, y;
	Point(double x=0, double y=0): x(x), y(y) {}					//    
	Point operator + (Point p) {return Point(x+p.x, y+p.y);}				//     
	Point operator - (Point p) {return Point(x-p.x, y-p.y);}				//     
	Point operator * (double k) {return Point(k*x, k*y);}				//     
	Point operator / (double k) {return Point(x/k, y/k);}				//     （      ）
	bool operator < (const Point &p) const {return x!=p.x ? (x Polygon;

2)判断点とベクトルの位置関係

int ccw(Point p0, Point p1, Point p2) {
	Vector v1 = p1-p0;
	Vector v2 = p2-p0;
	if(v1.cross(v2) > 0) return 1;			//     
	if(v1.cross(v2) < 0) return -1;			//     
	if(v1.dot(v2) < 0) return 2;			//         
	if(v1.norm() < v2.norm()) return -2;	//         
	return 0;								//    
}

3)アンドリューアルゴリズムO(n＊log(n)))

Polygon convexHull(Polygon source) {
	if(source.size() < 3) return source;	//         ，       
	Polygon upper, lower;			//       
	sort(source.begin(), source.end());	//        
	upper.push_back(source[0]);
	upper.push_back(source[1]);
	lower.push_back(source[source.size()-1]);
	lower.push_back(source[source.size()-2]);
	for(int i=2; i=1 && ccw(upper[n-1], upper[n], source[i])!=-1; --n)
			upper.pop_back();		//             
		upper.push_back(source[i]);
	}
	for(int i=source.size()-3; i>=0; --i) {	//      
		for(int n=lower.size()-1; n>=1 &&ccw(lower[n-1], lower[n], source[i])!=-1; --n)
			lower.pop_back();		//             
		lower.push_back(source[i]);
	}
	for(int i=1; i

2.他のデータ構造

  ：
struct Segment {
    Point p1, p2;
};

  ：
typedef Segment Line;

 ：
struct Circle {
    Point o;			//  
    double radius;		//  
}

3.その他のアルゴリズム
1)直線の直交と平行判断
まず二つの直線に対応するベクトルを求めます.
二つのベクトルの内積は0で、二つの直線が直交します.
二つのベクトルの外積は0で、二つの直線は平行です.
2)投影法

Point project(Segment s, Point p) {
	Vector base = s.p2 - s.p1;
	double r = (p-s.p1).dot(base)/base.norm();
	return s.p1 + base*r;
}

3)イメージ(直線の対称点について)

Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p)*2.0;
}

4)距離

     ： 

       ：
double getDist(Line l, Point p) {
	return abs((l.p2-l.p1).cross(p-l.p1) / (l.p2-l.p1).abs());
}

       :
double getDist(Segment s, Point p) {
	if((s.p2-s.p1).dot(p-s.p1) < 0) return (p-s.p1).abs();
	if((s.p1-s.p2).dot(p-s.p2) < 0) return (p-s.p2).abs();
	return abs((s.p2-s.p1).cross(p-s.p1) / (s.p2-s.p1).abs());
}

線分間の距離:
各線分の2つのエンドポイントから別の線分までの距離の中の最小値
5)2つの線分が交わるかどうかを判断する.

bool intersect(Point p1, Point p2, Point p3, Point p4) {
	return ccw(p1, p2, p3)*ccw(p1, p2, p4)<=0 &&
			ccw(p3, p4, p1)*ccw(p3, p4, p2)<=0;
}

6)二線の交点を求めます.

Point getCrossPoint(Segment s1, Segment s2) {
	Vector base = s2.p2 - s2.p1;
	double d1 = abs(base.cross(s1.p1-s2.p1));
	double d2 = abs(base.cross(s1.p2-s2.p1));
	double t = d1/(d1+d2);
	return s1.p1 + (s1.p2 - s1.p1)*t;
}

7)凸多角形の面積を計算する

double getArea(Polygon polygon) {
	double res = 0;
	for(int i=0; i

8)点が多角形内にあるかどうかを判断する

int contains(Polygon g, Point p) {
	int n = g.size();
	bool flag = false;
	for(int i=0; i b.y) swap(a, b);
		if(a.y<0 && b.y>0 && a.cross(b)>0) flag = !flag;
	}
	return flag ? 2 : 0;								//2   “ ”，0   “ ”
}

9)