# 計算幾何
## Template
### point

typedef double Double;
struct Point {
  Double x,y;

  bool operator < (const Point &b)const{    // 比較
    //return tie(x,y) < tie(b.x,b.y);
    //return atan2(y,x) < atan2(b.y,b.x);
  }
  Point operator + (const Point &b)const{   // 向量加法
    return {x+b.x,y+b.y};
  }
  Point operator - (const Point &b)const{   // 向量減法
    return {x-b.x,y-b.y};
  }
  Point operator * (const Double &d)const{  // 向量伸縮
    return {d*x, d*y};
  }
  Double operator * (const Point &b)const{  // 向量內積
    return x*b.x + y*b.y;
  }
  Double operator % (const Point &b)const{  // 向量外積
    return x*b.y - y*b.x;
  }
  Double abs(){
    return sqrt(x*x + y*y);
  }
  Double abs2(){
    return (x*x + y*y);
  }
};

---
## 問題
### 1. 點到直線距離
$\frac{|\vec u \times \vec v|}{|\vec v|}$

double dist_point_to_line(point &u, point &v){
	return abs((u%v)/abs(v));
}

### 2. 兩直線交點
$I=p+t\vec V$
$t=-\frac{|\vec W\times \vec {PQ}|}{|\vec V \times \vec W|}$

Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
    Point u = P-Q;
    double t = Cross(w,u) / Cross(v,w);
    return P + v*t;
}

### 3. 凸包

vector<Point> convexhull(vector<Point> &p){ // 輸入點，回傳凸包
	sort(p.begin(), p.end());
	int n = p.size();
	int m = 0;
	vector<Point> res;
	for(int i = 0; i < n; i++){
		while(m >= 2 && (p[i]-res[m-2]) % (res[m-1]-res[m-2]) < 0){
			res.pop_back();
			m--;
		}
		res.push_back(p[i]);
		m++;
	}
	for(int i = n-2; i >= 0; i--){
		while(m >= 2 && (p[i]-res[m-2]) % (res[m-1]-res[m-2]) < 0){
			res.pop_back();
			m--;
		}
		res.push_back(p[i]);
		m++;
	}
	return res;
}

### 4. 簡單多邊形面積

double _2d_area(vector<Point> &poly){ // 輸入簡單多邊形（起點和終點須重複, 已排序好） 回傳間單多邊形的面積
	int n = poly.size();
	double res = 0.0;
	for(int i = 0; i < n-1; i++){
		res += (poly[i] % poly[i+1]);
	}
	return abs(res/2);
}