2021 ccpc 桂林站 F
题目链接
题目大意：
给定两个凸包，保证内凸包严格在内求照亮边界的期望值，拿到题目一推就能发现题目实际是求
m条内凸包边右侧的外凸包边长和 * 该内凸包边长 的和 / 外凸包的总长。
思路：
双指针，准确来说是三指针，i 表示内凸包 p[i] --> p[i+1]（L) 的边，k 指向直线 L 与外凸包的终边 P[k] --> P[k+1]， j 指向 直线 L 与外凸包的起始边 P[j] --> P[j+1] 。
但注意不要使用直线与线段判交点 ， 正方形对角线数据 会使程序死循环。此外内凸包的边可能与所有外凸包边相交。
所以一个解决办法是用射线判断是否与线段相交------
考虑叉积， 很容易得出终边射线与外凸包相交条件是
bool chked(Point a, Point b, Point c, Point d){if(sgn((b-a)^(d-a))>0 && sgn((b-a)^(c-a))<=0) return true;return false;
}
即线段终点叉积大于零，起点叉积小于等于零，至于等号的选取条件，读者可以根据样例手推，取不取等号代表着对端点处的不同细节处理。 起点判断同上~~
然后这个题就是一个简单的指针扫描了~~~~
要是我上一次写出来了，也不至于这次才写出来
唉，菜鸡作茧自缚系列
#include <bits/stdc++.h>
#define In inline
#define pi (atan(1.0)*4)
#define enter puts("")
#define MaxN 0x3f3f3f3f
#define MinN 0xc0c0c0c0
#define pb push_back
#define bug(x) cerr<<#x<<'='<<x<<' '
#define ALL(a) a.begin(), a.end()
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define mset(a,b) memset(a,b,sizeof(a))
#define sz(a) (int)a.size()
#define eps 1e-6
#define buff ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
template<typename T>
T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>
T lcm(T a,T b){return a*b/gcd(a,b);}
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int MOD = 1e9+7;
In ll read()
{ll ans = 0;char ch = getchar(), las = ' ';while(!isdigit(ch)) las = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(las == '-') ans = -ans;return ans;
}
In void write(ll x)
{if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x%10 + '0');
}
typedef long double db;
int sgn(db x){if(fabs(x) < eps) return 0;return x < 0 ? -1 : 1;
}
struct Point{db x, y;Point(){} Point(db x, db y):x(x), y(y){}void input(){scanf("%Lf%Lf", &x, &y);}Point operator +(Point b){return Point(x+b.x,y+b.y);}Point operator -(Point b){return Point(x-b.x,y-b.y);}db operator ^(Point b){return x*b.y-y*b.x;}db distance(Point b){return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));}
};
const int N = 2e5+10;
Point P[N], p[N];
bool chkst(Point a, Point b, Point c, Point d){if(sgn((b-a)^(c-a))<0 && sgn((b-a)^(d-a))>=0) return true;return false;
}
bool chked(Point a, Point b, Point c, Point d){if(sgn((b-a)^(d-a))>0 && sgn((b-a)^(c-a))<=0) return true;return false;
}
Point cross_p(Point a, Point b, Point c, Point d){db a1 = (d-c)^(a-c);db a2 = (d-c)^(b-c);
// cout << "a---- " << a1 << ' ' << a2 << endl; return Point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
}
db d[N], Sum;
void run_case(){int n = read(), m = read();rep(i, 0, n-1) P[i].input();rep(i, 0, m-1) p[i].input();rep(i, 0, n-1) d[i] = P[i].distance(P[(i+1)%n]), Sum += d[i];db now = 0, tot = 0;int i = 0, j = 0, k = 0;while(!chkst(p[(i+1)%m], p[i], P[j], P[(j+1)%n])){j = (j+1)%n;}k = j;db l, r;while(i < m){l = P[j].distance(cross_p(p[i], p[(i+1)%m], P[j], P[(j+1)%n]));while(!chked(p[i], p[(i+1)%m], P[k], P[(k+1)%n])){now += d[k];k = (k+1)%n;}r = P[k].distance(cross_p(p[i], p[(i+1)%m], P[k], P[(k+1)%n]));tot += p[i].distance(p[(i+1)%m])*(now-l+r);i ++;while(!chkst(p[(i+1)%m], p[i], P[j], P[(j+1)%n])){now -= d[j];j = (j+1)%n;}}printf("%.15Lf\n", tot / Sum);
}int main()
{
// freopen("C:\\Users\\MARX HE\\Desktop\\input.txt","r",stdin);
// freopen("C:\\Users\\MARX HE\\Desktop\\output.txt","w",stdout);int _ = 1;
// int _ = read();while(_ --){run_case();}
}
发布评论