第七個專題了，初期計(jì)算幾何：

(1)、基本公式

拿了白書上面的三個例題做做。。。

1、uva 11178題意：作三角形ABC每個內(nèi)角的三等分線，相交成三角形DEF，則DEF是等邊三角形。已知A，B，C三點(diǎn)坐標(biāo)，問D,E,F三點(diǎn)坐標(biāo)。分析：簡單的求直線交點(diǎn)、內(nèi)角等分線可以通過直線旋轉(zhuǎn)角度求出。

#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long LL;const double EPS = 1e-10;const int INF = 0x3f3f3f3f;const int N = 310;int dcmp(double x) {return abs(x) < EPS ? 0 : x < 0 ? 1 : -1;}struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline void in() { scanf("%lf %lf", &x, &y); }    inline double length() { return sqrt(x * x + y * y); }};inline po Operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentPRoperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷一個點(diǎn)是否在一條線段上（不包含端點(diǎn)）.bool Onsegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q點(diǎn)到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}po solve(po a, po b, po c){    po v1 = rot(c - b, angle(a - b, c - b) / 3);    po v2 = rot(b - c, -angle(a - c, b - c) / 3);    return getlineintersection(b, v1, c, v2);}int main() {    int t;    scanf("%d", &t);    while (t--){        po a, b, c;        a.in(); b.in(); c.in();        po d = solve(a, b, c), e = solve(b, c, a), f = solve(c, a, b);        printf("%.6f %.6f %.6f %.6f %.6f %.6f/n", d.x, d.y, e.x, e.y, f.x, f.y);    }    return 0;}
2、uvalive 3263
題意：給定一個一筆畫構(gòu)成的平面圖的點(diǎn)、求出這一筆畫把整個平面分成了幾個部分。分析：根據(jù)歐拉定理可以求出面數(shù)，假設(shè)一個平面圖的點(diǎn)數(shù)為V，邊數(shù)為E，則面數(shù)F = E + 2 – V。點(diǎn)數(shù)可以把所有直線的交點(diǎn)求出后去重得出、至于邊數(shù)，可以枚舉每一個點(diǎn)，如果一個點(diǎn)在一條邊上，那么增加一條邊。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const double EPS = 1e-10;const int INF = 0x3f3f3f3f;const int N = 310;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline void in() { scanf("%lf %lf", &x, &y); }    inline void out() { printf("%f %f", x, y); }    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}po p[N], v[N*N];int main() {    int n, k = 0;    while (scanf("%d", &n), n) {        for (int i = 0; i < n; i++) p[i].in();        memcpy(v, p, sizeof(po) * n);        n--;        int e = n, c = n;        for (int i = 0; i < n; i++)            for (int j = i + 2; j < n; j++)                if (SegmentProperIntersection(p[i], p[i+1], p[j], p[j+1]))                    v[c++] = intersection(p[i], p[i+1], p[j], p[j+1]);        sort(v, v + c);        c = unique(v, v + c) - v;        for (int i = 0; i < c; i++)            for (int j = 0; j < n; j++)                if (OnSegment(v[i], p[j], p[j+1])) e++;        printf("Case %d: There are %d pieces./n", ++k, e + 2 - c);    }    return 0;}
3、uva 11796
題意：兩條狗勻速分別沿著折線跑，已知同時(shí)出發(fā)，同時(shí)到達(dá)，求奔跑過程中兩條狗最大、最小距離的差值。分析：直接求解比較麻煩、因?yàn)樗俣任粗視r(shí)間未知而且奔跑的路線是一條折線。但是我們可以首先解決奔跑路線都是一條線段時(shí)的簡單子問題，以第一條狗為參照物、這樣就是求點(diǎn)到線段的距離了。而且可以知道兩條狗的速度之比為各自的距離之比，時(shí)間對于答案無影響，所以可以假設(shè)速度分別為各自的總距離。這樣從最起點(diǎn)開始，首先判斷誰先到達(dá)下一個點(diǎn)，然后求出這個過程當(dāng)中的最大最小距離，最大距離一定在第二條狗的路線的端點(diǎn)處求得，最小距離即為求點(diǎn)到線段的距離。每次一定有一條狗到達(dá)下一個點(diǎn)，那么整個問題就可以分解為A + B個簡單的子問題了。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;const double EPS = 1e-10;const double INF = 0x3f3f3f3f;const double PI = acos(-1.0);const int N = 60;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) { return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {//線段相交判定    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po p, po a, po b) {//求出點(diǎn)p到線段ab之間的距離    if (a == b) return (p - a).length();    po v1 = b - a, v2 = p - a, v3 = p - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}double area(int n, po* p) {//求出任意多邊形的有向面積。    double ans = 0;    for (int i = 0; i < n - 1; i++) ans += det(p[i] - p[0], p[i+1] - p[0]);    return ans / 2;}bool isconvexhull(po* p, int n) {//判斷該多邊形是否為凸包    int tag = dcmp(det(p[1] - p[0], p[2] - p[1]));    for (int i = 1; i < n; i++)        if (tag * dcmp(det(p[i+1] - p[i], p[i+2] - p[i+1])) < 0) return 0;    return 1;}bool ispointinpolygon(po* p, int n, po c) {//判斷c點(diǎn)是否在多邊形內(nèi)    bool flag = 0;    for (int i = 0, j = n - 1; i < n; j = i++) {    if (((p[i].y > c.y) != (p[j].y > c.y)) && (c.x < (p[j].x - p[i].x) * (c.y - p[i].y) / (p[j].y - p[i].y) + p[i].x))        flag = !flag;    }    return flag;}vector<po> convexhull(po* p, int n) {//求出頂點(diǎn)數(shù)組構(gòu)成的凸包    sort(p, p + n);    int k = 0;    vector<po> q(n << 1);    for (int i = 0; i < n; i++) {        while (k > 1 && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    for (int i = n - 2, t = k; i >= 0; i--) {        while (k > t && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    q.resize(k - 1);    return q;}double ma, mi;void update(po p, po a, po b) {    mi = min(mi, DistanceToSegment(p, a, b));    ma = max(ma, (p - a).length());    ma = max(ma, (p - b).length());}po pa[N], pb[N];int main() {    int t, ca = 0;    scanf("%d", &t);    while (t--) {        int a, b;        scanf("%d %d", &a, &b);        for (int i = 0; i < a; i++) scanf("%lf %lf", &pa[i].x, &pa[i].y);        for (int i = 0; i < b; i++) scanf("%lf %lf", &pb[i].x, &pb[i].y);        ma = -INF, mi = INF;        int f = 0, s = 0;        double lena = 0, lenb = 0;        for (int i = 1; i < a; i++) lena += (pa[i] - pa[i-1]).length();        for (int i = 1; i < b; i++) lenb += (pb[i] - pb[i-1]).length();        while (f < a - 1 && s < b - 1) {            double la = (pa[f+1] - pa[f]).length(), lb = (pb[s+1] - pb[s]).length();            double ti = min(la / lena, lb / lenb);            po va = (pa[f+1] - pa[f]) / la * lena * ti, vb = (pb[s+1] - pb[s]) / lb * lenb * ti;            update(pa[f], pb[s], pb[s] + vb - va);            pa[f] = pa[f] + va; pb[s] = pb[s] + vb;            if (pa[f] == pa[f+1]) f++;            if (pb[s] == pb[s+1]) s++;        }        printf("Case %d: %.0f/n", ++ca, ma - mi);    }    return 0;}
(2)、點(diǎn)積和叉積的運(yùn)用
1、poj2031題意：給出三維坐標(biāo)系上的一些球的球心坐標(biāo)和其半徑，搭建通路，使得他們能夠相互連通。如果兩個球有重疊的部分則算為已連通，無需再搭橋。求搭建通路的最小費(fèi)用（費(fèi)用就是邊權(quán)，就是兩個球面之間的距離）。分析：就是使得所有點(diǎn)聯(lián)通的最小代價(jià)、明顯的最小生成樹，如果兩個球有公共部分，則他們之間的邊權(quán)就為0.直接prim求解即可。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N = 110;const double EPS = 1e-6;const double INF = 0x3f3f3f3f;double dis[N][N], d[N];bool vis[N];struct po { double x, y, z, r; } p[N];void init(int n) {    fill(d + 1, d + n, INF);    memset(vis, 0, 4 * n);}double prim(int n) {    init(n+2);    double res = 0;    while (1) {        int v = -1;        for (int u = 0; u < n; u++)            if (!vis[u] && (v == -1 || d[u] < d[v])) v = u;        if (v == -1) break;        vis[v] = 1; res += d[v];        for (int u = 0; u < n; u++)            d[u] = min(d[u], dis[v][u]);    }    return res;}int main() {    int n;    while (scanf("%d", &n), n) {        for (int i = 0; i < n; i++) scanf("%lf %lf %lf %lf", &p[i].x, &p[i].y, &p[i].z, &p[i].r);        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                double d = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y) + (p[i].z - p[j].z) * (p[i].z - p[j].z));                d -= p[i].r + p[j].r;                dis[i][j] = dis[j][i] = d > EPS ? d : 0;            }        }        printf("%.3f/n", prim(n));    }    return 0;}
2、poj1039題意：有一寬度為1的折線管道,上面頂點(diǎn)為(xi,yi),所對應(yīng)的下面頂點(diǎn)為(xi,yi-1),假設(shè)管道都是不透明的,不反射的,光線從左邊入口處的(x1,y1),(x1,y1-1)之間射入,向四面八方傳播,求解光線最遠(yuǎn)能傳播到哪里(取x坐標(biāo))或者是否能穿透整個管道.分析：光線最優(yōu)時(shí)一定會經(jīng)過一個上頂點(diǎn)和一個下頂點(diǎn)，否則總可以把光線進(jìn)行旋轉(zhuǎn)然后使得光線傳播到更遠(yuǎn)的地方，這樣，我們只需要枚舉上頂點(diǎn)和下頂點(diǎn)，然后求出一束光線最遠(yuǎn)可以與哪根管道相交，只需要判斷管道彎曲處的垂直x軸的線段，如果光線與該線段相交，那么則證明光線一定與彎曲處的管道的上壁或者下壁相交。每次取最大值即可。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;const double EPS = 1e-10;const double INF = 0x3f3f3f3f;const int N = 30;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}double area(po* p, int n) {    double ans = 0;    for (int i = 0; i < n - 1; i++) ans += det(p[i] - p[0], p[i+1] - p[0]);    return ans / 2;}po p[N], p1[N];int main() {    int n;    while (scanf("%d", &n), n) {        for (int i = 1; i <= n; i++) {            double x, y;            scanf("%lf %lf", &x, &y);            p[i] = po(x, y); p1[i] = po(x, y - 1);        };        double ans = -INF;        bool flag = 1;        for (int i = 1; i <= n && flag; i++) {            for (int j = 1; j <= n && flag; j++) {                if (i != j) {                    po b; int k;                    for (k = 1; k <= n; k++) {                        b = intersection(p[i], p1[j], p1[k], p[k]);                        if (dcmp(b.y - p1[k].y) < 0 || dcmp(b.y - p[k].y) > 0) break;                    }                    if (k == n + 1) flag = 0;                    else if (k > max(i, j)) {                        b = intersection(p[i], p1[j], p[k], p[k-1]);                        if (dcmp(b.x - p[k-1].x) >= 0 && dcmp(b.x - p[k].x) <= 0) ans = max(ans, b.x);                        b = intersection(p[i], p1[j], p1[k], p1[k-1]);                        if (dcmp(b.x - p1[k-1].x) >= 0 && dcmp(b.x - p1[k].x) <= 0) ans = max(ans, b.x);                    }                }            }        }        flag ? printf("%.2f/n", ans) : puts("Through all the pipe.");    }    return 0;}
(3)、多邊形的簡單算法
1、  poj1408
題意：有一個1*1的正方形，分別給出下，上，左，右邊每個邊上的n個點(diǎn)，對邊對應(yīng)點(diǎn)連線，問這些線段相交的最大的四邊形面積是多少。分析：求多邊形面積可以用簡單的叉積實(shí)現(xiàn)，這樣，算出所有的多邊形面積取最大值就行了。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const double EPS = 1e-10;const int INF = 0x3f3f3f3f;const int N = 40;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline void in() { scanf("%lf %lf", &x, &y); }    inline void out() { printf("%f %f", x, y); }    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}double area(po a, po b, po c, po d) {    return (det(b - a, c - a) + det(c - a, d - a)) / 2;}po a[N], b[N], c[N], d[N], t[N][N];int main() {    int n;    while (scanf("%d", &n), n) {        double in;        for (int i = 1; i <= n; i++) scanf("%lf", &in), a[i] = po(in, 0);        for (int i = 1; i <= n; i++) scanf("%lf", &in), b[i] = po(in, 1);        for (int i = 1; i <= n; i++) scanf("%lf", &in), c[i] = po(0, in);        for (int i = 1; i <= n; i++) scanf("%lf", &in), d[i] = po(1, in);        t[0][0] = po(0, 0); t[0][n+1] = po(1, 0);        for (int i = 1; i <= n; i++) t[0][i] = a[i];        t[n+1][0] = po(0, 1); t[n+1][n+1] = po(1, 1);        for (int i = 1; i <= n; i++) t[n+1][i] = b[i];        for (int i = 1; i <= n; i++) {            t[i][0] = c[i];            for (int j = 1; j <= n; j++) {                t[i][j] = intersection(c[i], d[i], a[j], b[j]);            }            t[i][n+1] = d[i];        }        double ans = 0;        for (int i = 0; i <= n; i++)            for (int j = 0; j <= n; j++) ans = max(ans, abs(area(t[i][j], t[i+1][j], t[i+1][j+1], t[i][j+1])));        printf("%.6f/n", ans);    }    return 0;}
2、  poj1584
題意：按照順時(shí)針或逆時(shí)針方向輸入一個n邊形的頂點(diǎn)坐標(biāo)集，先判斷這個n邊形是否為凸包。再給定一個圓形（圓心坐標(biāo)和半徑），判斷這個圓是否完全在n邊形內(nèi)部。分析：要判斷一個多邊形是否為凸包、我們只需要從第一個點(diǎn)開始，依次判斷第一條邊向量與后面一條邊向量的叉積，這個叉積可以決定方向是順時(shí)針還是逆時(shí)針、這樣，如果計(jì)算時(shí)出現(xiàn)順時(shí)針與逆時(shí)針則證明不是凸包，這個自己手動模擬下即可。至于判斷圓是否在多邊形內(nèi)，我們只需要類似判斷三角形內(nèi)圓的方式判斷、也就是圓心到每條邊的距離不小于半徑、不過首先圓心必須在多邊形內(nèi)。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;const double EPS = 1e-10;const double INF = 0x3f3f3f3f;const double PI = acos(-1.0);const int N = 110;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}double area(po* p, int n) {    double ans = 0;    for (int i = 0; i < n - 1; i++) ans += det(p[i] - p[0], p[i+1] - p[0]);    return ans / 2;}po p[N], c;int tag;bool isconvexhull(int n) {    tag = dcmp(det(p[1] - p[0], p[2] - p[1]));    for (int i = 1; i < n; i++)        if (tag * dcmp(det(p[i+1] - p[i], p[i+2] - p[i+1])) < 0) return 0;    return 1;}bool ispointinpolygon(int n) {    bool flag = 0;    for (int i = 0, j = n - 1; i < n; j = i++) {    if (((p[i].y > c.y) != (p[j].y > c.y)) && (c.x < (p[j].x - p[i].x) * (c.y - p[i].y) / (p[j].y - p[i].y) + p[i].x))        flag = !flag;    }    return flag;}int main() {    int n;    double r;    while (scanf("%d", &n), n >= 3) {        scanf("%lf %lf %lf", &r, &c.x, &c.y);        for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);        p[n] = p[0], p[n+1] = p[1];        bool flag = isconvexhull(n);        if (flag) {            flag &= ispointinpolygon(n);            for (int i = 0; i < n && flag; i++) {                double s = abs(det(p[i] - c, p[i+1] - c));                if (dcmp(s / (p[i+1] - p[i]).length() - r) == -1) flag = 0;            }            puts(flag ? "PEG WILL FIT" : "PEG WILL NOT FIT");        }        else puts("HOLE IS ILL-FORMED");    }    return 0;}
(4)、凸包
1、  poj2187
題意：給定n個點(diǎn)，求最遠(yuǎn)點(diǎn)對。分析：枚舉效率太低，但是可以知道最遠(yuǎn)點(diǎn)對一定出現(xiàn)在這n個點(diǎn)的凸包中，對于這n個點(diǎn)的凸包，兩兩枚舉即可。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;const double EPS = 1e-10;const int INF = 0x3f3f3f3f;const int N = 50010;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline void in() { scanf("%lf %lf", &x, &y); }    inline void out() { printf("%f %f", x, y); }    inline double length() { return sqrt(x * x + y * y); }};inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) {return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}double area(po a, po b, po c, po d) {    return (det(b - a, c - a) + det(c - a, d - a)) / 2;}po p[N];vector<po> convex_hull(po* p, int n) {    sort(p, p + n);    int k = 0;    vector<po> q(n << 1);    for (int i = 0; i < n; i++) {        while (k > 1 && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    for (int i = n - 2, t = k; i >= 0; i--) {        while (k > t && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    q.resize(k - 1);    return q;}int main() {    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++) p[i].in();    vector<po> q = convex_hull(p, n);    double res = 0;    for (int i = 0; i < q.size(); i++)        for (int j = 0; j < i; j++) res = max(res, (q[i] - q[j]).length());    printf("%.0f/n", res * res);    return 0;}
2、  poj1113
題意：給一個多邊形、求一個圈包圍整個多邊形且這個圈離多邊形的距離不能小于給定的L，求最小的圈的長度。分析：可以知道如果圈離最外圍的點(diǎn)的距離大于L，離里面的點(diǎn)的距離也會大于L，那么只需要求出包含這個多邊形的凸包的圈的最小長度，手動畫圖加上猜想與推理可以知道圈有一些半徑為L的圓的圓弧與一些線段組成且長度就為一個完整的圓的周長加上凸包的周長。
#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <vector>using namespace std;const double EPS = 1e-10;const double INF = 0x3f3f3f3f;const double PI = acos(-1.0);const int N = 110;int dcmp(double x) { return abs(x) < EPS ? 0 : x < 0 ? -1 : 1; }struct po {    double x, y;    po(double x = 0, double y = 0) : x(x), y(y) {}    inline double length() { return sqrt(x * x + y * y); }};po p[N];inline po operator + (po a, po b) { return po(b.x + a.x, b.y + a.y); }inline po operator - (po a, po b) { return po(a.x - b.x, a.y - b.y); }inline po operator * (po a, double d) { return po(a.x * d, a.y * d); }inline po operator / (po a, double d) { return po(a.x / d, a.y / d); }inline bool operator < (const po &a, const po &b)  { return a.x == b.x ? a.y < b.y : a.x < b.x; }inline bool operator == (const po &a, const po &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }inline double dot(po a, po b) { return a.x * b.x + a.y * b.y; }//點(diǎn)積inline double det(po a, po b) { return a.x * b.y - a.y * b.x; }//叉積//求出以向量a繞起點(diǎn)逆時(shí)針旋轉(zhuǎn)a角度之后該向量的坐標(biāo)inline po rot(po a, double rad) { return po(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }double angle(po a, po b) { return acos(dot(a, b) / a.length() / b.length()); }//求向量a和b之間的角度double area(po a, po b, po c) { return det(b - a, c - a); }//求出以ab、ac為鄰邊組成的三角形的面積inline po normal(po a) {    double l = a.length();    return po(-a.y / l, a.x / l);}//求出直線p1+tv和直線q+tw的交點(diǎn)，v和w為方向向量po getlineintersection(po p, po v, po q, po w) {    po u = p - q;    double t = det(w, u) / det(v, w);    return p + v * t;}//求出p1、p2點(diǎn)確定的直線與q1、q2點(diǎn)確定的直線的交點(diǎn)，使用確保兩條直線不會平行po intersection(po p1, po p2, po q1, po q2) { return p1 + (p2 - p1) * det(q2 - q1, q1 - p1) / det(q2 - q1, p2 - p1); }//線段相交判定bool SegmentProperIntersection(po a1, po a2, po b1, po b2) {    double c1 =  det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),           c3 =  det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}//判斷q點(diǎn)是否在p1、p2點(diǎn)組成的線段上//bool on_seg(po p1, po p2, po q) { return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0; }bool OnSegment(po p, po a1, po a2) { return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0; }double DistanceToLine(po q, po a, po b) {//求出q到直線ab的距離。    po v1 = b - a, v2 = q - a;    return abs(det(v1, v2)) / v1.length();}double DistanceToSegment(po q, po a, po b) {//求出點(diǎn)q到線段ab之間的距離    if (a == b) return (q - a).length();    po v1 = b - a, v2 = q - a, v3 = q - b;    if (dcmp(dot(v1, v2)) < 0) return v2.length();    if (dcmp(dot(v1, v3)) > 0) return v3.length();    return abs(det(v1, v2)) / v1.length();}po GetLinePorjection(po q, po a, po b) {//獲得點(diǎn)q在直線ab上的投影    po v = b - a;    return a + v * dot(v, q - a) / dot(v, v);}//求出任意多邊形的有向面積。double area(int n) {    double ans = 0;    for (int i = 0; i < n - 1; i++) ans += det(p[i] - p[0], p[i+1] - p[0]);    return ans / 2;}//判斷該多邊形是否為凸包bool isconvexhull(int n) {    int tag = dcmp(det(p[1] - p[0], p[2] - p[1]));    for (int i = 1; i < n; i++)        if (tag * dcmp(det(p[i+1] - p[i], p[i+2] - p[i+1])) < 0) return 0;    return 1;}//判斷c點(diǎn)是否在多邊形內(nèi)bool ispointinpolygon(int n, po c) {    bool flag = 0;    for (int i = 0, j = n - 1; i < n; j = i++) {    if (((p[i].y > c.y) != (p[j].y > c.y)) && (c.x < (p[j].x - p[i].x) * (c.y - p[i].y) / (p[j].y - p[i].y) + p[i].x))        flag = !flag;    }    return flag;}//求出頂點(diǎn)數(shù)組構(gòu)成的凸包vector<po> convexhull(int n) {    sort(p, p + n);    int k = 0;    vector<po> q(n << 1);    for (int i = 0; i < n; i++) {        while (k > 1 && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    for (int i = n - 2, t = k; i >= 0; i--) {        while (k > t && det(q[k-1] - q[k-2], p[i] - q[k-1]) <= 0) k--;        q[k++] = p[i];    }    q.resize(k - 1);    return q;}int main() {    int n, l;    while (~scanf("%d %d", &n, &l)) {        for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);        vector<po> t = convexhull(n);        int len = t.size() - 1;        double ans = 0;        for (int i = 0; i < len; i++) ans += (t[i+1] - t[i]).length();        ans += (t[len] - t[0]).length();        printf("%.0f/n", ans + 2 * PI * l);    }    return 0;}