栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2623 Area

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2623 Area

#include <cstdio>#include <algorithm>const double eps = 1e-7;struct pt {double x, y;pt(const double _x = .0, const double _y = .0):x(_x), y(_y) { }void scan() { scanf("%lf %lf", &x, &y); }} p[2][51], s, t;inline pt operator+(const pt &a, const pt &b) { return pt(a.x + b.x, a.y + b.y); }inline pt operator-(const pt &a, const pt &b) { return pt(a.x - b.x, a.y - b.y); }inline pt operator*(const pt &a, const double &b) { return pt(a.x * b, a.y * b); }int n[2], m;inline double cpr(const pt &o, const pt &a, const pt &b){ return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x); }inline double dpr(const pt &o, const pt &a, const pt &b){ return (a.x-o.x)*(b.x-o.x) + (a.y-o.y)*(b.y-o.y); }inline int sgn(const double d) { return d < -eps ? -1 : (d > eps); }inline pt ip(const pt &a, const pt &b, const pt &c, const pt &d){ return (b - a) * (cpr(a, d, c) / (cpr(a, d, b) + cpr(a, b, c))) + a; }inline void adjust(pt a[], const int n){double area = .0;a[n] = a[0];for (int i = 0; i < n; ++i)area += cpr(pt(), a[i], a[i+1]);if (sgn(area) < 0) {std::reverse(a, a+n);a[n] = a[0];}}struct pr {double rat;int inc;pr(const double _rat = .0, const int _inc = 0):rat(_rat), inc(_inc) { }} e[200];inline bool operator<(const pr &a, const pr &b){ return a.rat < b.rat || (a.rat == b.rat && a.inc < b.inc); }int cnt;inline void insert(const pt &x, const int inc){e[cnt++] = pr(sgn(t.x - s.x) ? (x.x - s.x) / (t.x - s.x) : (x.y - s.y) / (t.y - s.y), inc);}inline double solve(){int c0, c1, c2, c3;double res = .0;for (int i = 0; i < m; ++i)for (int k = 0; k < n[i]; ++k) {s = p[i][k], t = p[i][(k+1)%n[i]];if (sgn(cpr(pt(), s, t)) == 0) continue;cnt = 0;e[cnt++] = pr(0.0, 1);e[cnt++] = pr(1.0, -1);for (int j = 0; j < m; ++j) {if (i == j) continue;for (int l = 0; l < n[j]; ++l) {pt &p0 = p[j][(l-1+n[j])%n[j]], &p1 = p[j][l], &p2 = p[j][(l+1)%n[j]], &p3 = p[j][(l+2)%n[j]];c0 = sgn(cpr(s, t, p0));c1 = sgn(cpr(s, t, p1));c2 = sgn(cpr(s, t, p2));if (c1 * c2 < 0)insert(ip(s, t, p1, p2), c2);else if (!c1 && c0 * c2 < 0)insert(p1, c2);else if (!c1 && !c2) {int dp = sgn(dpr(pt(), t - s, p2 - p1));if (dp > 0 && j > i) {insert(p1, -1);insert(p2, 1);}c0 = sgn(cpr(p1, p2, p0));c3 = sgn(cpr(p1, p2, p3));if (c0 < 0) insert(p1, dp);if (c3 < 0) insert(p2, -dp);}}}std::sort(e, e+cnt);int sum = 0;double total = .0, last = .0;for (int j = 0; j < cnt; ++j) {sum += e[j].inc;if (sum == 0 && e[j].inc == -1)total += e[j].rat - last;last = e[j].rat;}res += total * cpr(pt(), s, t);}return res * .5;}int main(){m = 2;while (~scanf("%d%d", &n[0], &n[1])) {for (int i = 0; i < n[0]; ++i) p[0][i].scan(); adjust(p[0], n[0]);for (int i = 0; i < n[1]; ++i) p[1][i].scan(); adjust(p[1], n[1]);printf("%.3fn", solve());}}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375864.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号