本文共 1727 字，大约阅读时间需要 5 分钟。
题意：给你一堆黑点一堆红点，问你有最多几个黑点能找到三个红点，使这个黑点在三角形内？
思路：显然红点组成的凸包内的所有黑点都能做到。但是判断黑点和凸包的关系朴素方法使O（n^2），显然超时。那么我现在有一个更好的方法判断点和凸包的关系。我固定一个红点，然后找连续两个红点使黑点 i 在这个三角形内（向量判），然后用二分查找是否存在这样的两个连续红点。这样复杂度为nlogn。
注意凸包不要用atan2的那种，会有精度误差...
代码：
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1e4 + 10;const int M = maxn * 30;const ull seed = 131;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;struct point{ double x,y;}p[100000],a[100000],b[100000], g;int n, tot;bool cmp(point A,point B){ if(A.x!=B.x) return A.x 1&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--; p[tot++]=a[i]; } int k=tot; for(int i=n-1;i>0;i--) { while(tot>k&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--; p[tot++]=a[i]; } if(n>1)tot--;}double turn(point st, point en, point q){ //正数:点在向量左侧 //负数:点在向量右侧 //0:点在向量直线上 return (st.x - q.x) * (en.y - q.y) - (en.x - q.x) * (st.y - q.y);}int mid(){ int l, r; l = 1, r = tot - 2; while(l <= r){ int m = (l + r) >> 1; if(turn(p[0], p[m], g) >= 0 && turn(p[0], p[m + 1], g) <= 0){ if(turn(p[m], p[m + 1], g) >= 0) return 1; return 0; } if(turn(p[0], p[m], g) >= 0){ l = m + 1; } else{ r = m - 1; } } return 0;}int main(){ int m; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y); sort(a+1,a+1+n,cmp); dopack();// for(int i = 0; i < tot; i++){// printf("* %lf %lf\n", p[i].x, p[i].y);// } scanf("%d", &m); int ans = 0; for(int i = 1; i <= m; i++){ scanf("%lf%lf", &g.x, &g.y); ans += mid(); } printf("%d\n", ans); return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/10821551.html