计算几何

The 2019 ICPC Asia Nanjing Regional Contest
https://codeforces.com/gym/103466/problem/K
因为精度问题WA了两发，第一次精度设置太高了导致有的数据如答案恰好是边界的点二分没找到，
第二次因为精度设置太低了导致WA了！
特判一下答案恰好是给的其中的一个点即可！
/*
1
-7 0 0 0 -6 7 -3.5 0
-6 7
*/
#include<iostream>
#include<cmath>
using namespace std;

typedef long double LD;
const LD eps = 1e-10;
LD S,length;
struct Line {
    LD x1,y1,x2,y2;
}lines[10];

int sign(LD x) {
    if(fabsl(x) <= eps) return 0;
    if(x > 0) return 1;
    return -1;
}

LD dot(LD x1,LD y1,LD x2,LD y2) {
    return x1 * x2 + y1 * y2;
}

LD det(LD x1,LD y1,LD x2,LD y2) {
    return x1 * y2 - x2 * y1;
}

LD area(LD x1,LD y1,LD x2,LD y2,LD x3,LD y3) {
    return det(x3 - x1,y3 - y1,x2 - x1,y2 - y1);
}

bool is_segment(int p,LD px,LD py) {
    LD x1 = lines[p].x1,y1 = lines[p].y1,x2 = lines[p].x2,y2 = lines[p].y2;
    return sign(area(px,py,x1,y1,x2,y2)) == 0 && sign(dot(x1 - px,y1 - py,x2 - px,y2 - py)) <= 0;
}

LD get_length(LD x,LD y) {
    return sqrtl(x * x + y * y);
}

LD dis_to_line(LD vx,LD vy,int p) {
    LD x1 = lines[p].x1,y1 = lines[p].y1,x2 = lines[p].x2,y2 = lines[p].y2;
    LD v1x = x2 - x1,v1y = y2 - y1,v2x = vx - x1,v2y = vy - y1;
    return fabsl(det(v1x,v1y,v2x,v2y)) / get_length(v1x,v1y);
}

int cmp(LD x,LD y) {
    if(fabsl(x - y) < eps) return 0;
    if(x > y) return 1;
    return -1;
}

bool check(LD midx,LD midy,int p) {
    LD dis = dis_to_line(midx,midy,p);
    if(cmp(dis * length,S / 2) >= 0) return true;
    return false;
}

int main() {
    int _;
    scanf("%d",&_);
    while(_--) {
        LD x1,y1,x2,y2,x3,y3,px,py;
        scanf("%LF%LF%LF%LF%LF%LF%LF%LF",&x1,&y1,&x2,&y2,&x3,&y3,&px,&py);
        int cnt = 0;
        lines[++cnt] = {x1,y1,x2,y2};
        lines[++cnt] = {x1,y1,x3,y3};
        lines[++cnt] = {x2,y2,x3,y3};
        bool ok = false;
        int p;
        for(int i=1; i<=3; i++) {
            if(is_segment(i,px,py)) {
                ok = true;
                p = i;
            }
        }
        if(!ok) puts("-1");
        else {
            LD vx,vy;
            if(p == 1) vx = x3,vy = y3;
            else if(p == 2) vx = x2,vy = y2;
            else vx = x1,vy = y1;
            LD dis = dis_to_line(vx,vy,p);
            LD L = get_length(lines[p].x2 - lines[p].x1,lines[p].y2 - lines[p].y1);
            S = dis * L;
            LD l1 = get_length(px - lines[p].x1,py - lines[p].y1);
            LD l2 = get_length(px - lines[p].x2,py - lines[p].y2);
            LD bx,by;
            if(l1 > l2) {
                bx = lines[p].x1,by = lines[p].y1;
                length = l1;
            } else {
                bx = lines[p].x2,by = lines[p].y2;
                length = l2;
            }
            LD lx = bx,ly = by,rx = vx,ry = vy;
            LD ansx = 0,ansy = 0;
            bool find = false;
            while(get_length(rx - lx,ry - ly) > eps) {
                LD midx = (lx + rx) / 2,midy = (ly + ry) / 2;
                if(check(midx,midy,p)) {
                    find = true;
                    ansx = midx,ansy = midy;
                    rx = midx,ry = midy;
                } else lx = midx,ly = midy;
            }
            if(!find) ansx = vx,ansy = vy;
            printf("%.10LF %.10LF\n",ansx,ansy);
        }
    }
    return 0;
}

计算任意多边形的面积！凸凹都可！ 
hdoj2036
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O)
    {
        return {x - O.x,y - O.y};
    }
} Points[N];

double dot(Point a,Point b) {
    return a.x * b.x + a.y * b.y;
}

double det(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double area(Point a,Point b,Point c) {
    return det(b - a,c - a);
}

int main() {
    int n;
    while(~scanf("%d",&n),n) {
        for(int i=1; i<=n; i++) {
            ll x,y;
            scanf("%lld%lld",&x,&y);
            Points[i] = {x,y};
        }
        double ans = 0;
        for(int i=2; i<=n-1; i++) {
            ans += area(Points[i],Points[i+1],Points[1]) / 2;
        }
        printf("%.1f\n",ans);
    }
    return 0;
}

//随机数据下凸包上点的个数为log(n)!
OI Wiki旋转卡壳 https://www.luogu.com.cn/problem/P1452
非正解，暴力竟然可以过。。。
凸包上的点远远小于n，所以n方枚举是可以过的要注意在一条边上的时候即：stk[top] == stk[top-1]，特判否则结果是零！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O) {
        return {x - O.x,y - O.y};
    }
}Points[N],e[N<<1];

bool operator < (Point &a,Point &b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double get_length(Point a) {
    return sqrt(a.x * a.x + a.y * a.y);
}

double cross(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double get_dis(Point p,Point a,Point b) {
    Point v1 = b - a,v2 = p - a;
    return fabs(cross(v1,v2) / get_length(v1));
}

ll get_two_dis(Point a,Point b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return (dx * dx + dy * dy);
}

int stk[N];
bool used[N];

double area(Point a,Point b,Point c) {
    return cross(b - a,c - a);
}

double ans;

void andrew(ll &n) {
    sort(Points+1,Points+n+1);
    int top = 0;
    for(int i=1; i<=n; i++) {
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) {
            if(area(Points[stk[top-1]],Points[stk[top]],Points[i]) < 0) {
                used[stk[top--]] = false;
            } else top--;
        }
        stk[++top] = i;
        used[i] = true;
    }
    used[1] = false;
    for(int i=n; i>=1; i--) {
        if(used[i]) continue;
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) top--;
        stk[++top] = i;
    }
    int num = top-1;
    for(int i=1; i<=num; i++) {
        int x = Points[stk[i]].x, y = Points[stk[i]].y;
        e[i] = e[i+num] = {x,y};
    }
    ll ans = 0;
    for(int i=1; i<num; i++) {
        for(int j=i+1; j<=num; j++) {
            ll x1 = e[i].x,y1 = e[i].y;
            ll x2 = e[j].x,y2 = e[j].y;
            ans = max(ans,get_two_dis({x1,y1},{x2,y2}));
        }
    }
    if(stk[top] == stk[top-1]) ans = get_two_dis(Points[1],Points[n]);
    printf("%lld\n",ans);
}

int main() {
    ll n,r;
    cin >> n;
    for(int i=1; i<=n; i++) {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        Points[i] = {x,y};
    }
    andrew(n);
    return 0;
}

思路枚举凸包上的点i,和i+1组成的一条边,然后三分，别忘了成环要2倍点的数量！
K - Blowing Candles
https://codeforces.com/gym/101635/attachments
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O) {
        return {x - O.x,y - O.y};
    }
}Points[N],e[N<<1];

bool operator < (Point &a,Point &b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double get_length(Point a) {
    return sqrt(a.x * a.x + a.y * a.y);
}

double cross(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double get_dis(Point p,Point a,Point b) {
    Point v1 = b - a,v2 = p - a;
    return fabs(cross(v1,v2) / get_length(v1));
}

double get_two_dis(Point a,Point b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int stk[N];
bool used[N];

double area(Point a,Point b,Point c) {
    return cross(b - a,c - a);
}

double ans;

void three_search(int x1,int y1,int x2,int y2,int num,int idx) {
    int l = idx + 2,r = l + num - 3;
    double res = 0;
    while(l <= r) {
        int lmid = l + (r - l) / 3,rmid = r - (r - l) / 3;
        double ldis = get_dis(e[lmid],{x1,y1},{x2,y2});
        double rdis = get_dis(e[rmid],{x1,y1},{x2,y2});
        if(rdis > ldis) l = lmid+1,res = rdis;
        else r = rmid-1,res = ldis;
    }
    ans = min(ans,res);
}

void andrew(ll &n) {
    sort(Points+1,Points+n+1);
    int top = 0;
    for(int i=1; i<=n; i++) {
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) {
            if(area(Points[stk[top-1]],Points[stk[top]],Points[i]) < 0) {
                used[stk[top--]] = false;
            } else top--;
        }
        stk[++top] = i;
        used[i] = true;
    }
    used[1] = false;
    for(int i=n; i>=1; i--) {
        if(used[i]) continue;
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) top--;
        stk[++top] = i;
    }

    //所有的边
    /*
    for(int i=1; i<top; i++) {
        printf("%d %d %d %d\n",Points[stk[i]].x,Points[stk[i]].y,Points[stk[i+1]].x,Points[stk[i+1]].y);
    }*/
    //cout<<"top = "<<top<<endl;
    int num = top-1;
    for(int i=1; i<=num; i++) {
        int x = Points[stk[i]].x, y = Points[stk[i]].y;
        e[i] = e[i+num] = {x,y};
    }
    for(int i=1; i<=num; i++) {
        int x1 = e[i].x, y1 = e[i].y;
        int x2 = e[i+1].x, y2 = e[i+1].y;
        three_search(x1,y1,x2,y2,num,i);
    }
}

int main() {
    ans = 1e18;
    ll n,r;
    cin >> n >> r;
    for(int i=1; i<=n; i++) {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        Points[i] = {x,y};
    }
    andrew(n);
    printf("%.15f\n",ans);
    return 0;
}

//极角排序
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;
struct Point {
    ll x,y;
    int id;
}Points[N];

bool cmp(Point a,Point b) {
    if(atan2(a.y,a.x) != atan2(b.y,b.x)) return atan2(a.y,a.x) < atan2(b.y,b.x);
    return a.x < b.x;
}

ll dot(Point a,Point b) {
    return a.x * b.x + a.y * b.y;
}

ll det(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        Points[i] = {x,y,i};
    }
    sort(Points+1,Points+n+1,cmp);
    int ans1 = 1,ans2 = n; //注意别忘了1,n之间的角度！
    for(int i=1; i<n; i++) {
        Point v1 = {dot(Points[i],Points[i+1]),abs(det(Points[i],Points[i+1]))};
        Point v2 = {dot(Points[ans1],Points[ans2]),abs(det(Points[ans1],Points[ans2]))}; //这里为啥有绝对值！
        if(det(v1,v2) > 0) ans1 = i,ans2 = i+1;
		//这里把向量点i和ans1旋转到x轴 坐标为 a.x * cos / |b| , a.y * sin / |b|;
		//之后若叉积为正则表示v2 在 v1 上方所以 i 和 i+1 的夹角更小！
    }
    cout<<Points[ans1].id<<" "<<Points[ans2].id<<"\n";
    return 0;
}