首页 > 代码库 > ZOJ 3720 Magnet Darts (计算几何，概率，判点是否在多边形内)

ZOJ 3720 Magnet Darts (计算几何，概率，判点是否在多边形内)

2024-07-14 04:22:47   218人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3720

题意：

在一个矩形区域投掷飞镖，因此飞镖只会落在整点上，投到每个点的得分是Ax+By。矩形区域里面有个多边形，如果飞镖投在多边形里面则得分，求最终的得分期望。

即：给定一个矩形内的所有整数点，判断这些点是否在一个多边形内

 

方法：

计算几何的判点是否在多边形内（几何模板），如果在，则令得分加(Ax+By)*以此点为中心边长为1的正方形面积

 1 void solve() 2 { 3     double ans = 0; 4     for (int i = p.x; i <= q.x; i++) 5     { 6         for (int j = p.y; j <= q.y; j++) 7         { 8             if (PointInPolygon(Point2D(i, j), poly.v, poly.n)) 9                 ans += (a * i + b * j) * (min(i + 0.5, q.x) - max(i - 0.5, p.x)) * (min(j + 0.5, q.y) - max(j - 0.5, p.y));10         }11     }12     printf("%.3f\n", ans / (q.x - p.x) / (q.y - p.y));13 }

 

代码：

  1 // #pragma comment(linker, "/STACK:102400000,102400000")  2 #include <cstdio>  3 #include <iostream>  4 #include <cstring>  5 #include <string>  6 #include <cmath>  7 #include <set>  8 #include <list>  9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn = 0; 23 const int maxm = 0; 24 const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 // const double INF = 1e30; 27 // const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32  33 typedef double db; 34 const double eps = 1e-7; 35 const double PI = acos(-1.0); 36 const double INF = 1e50; 37  38 const int POLYGON_MAX_POINT = 1024; 39  40 db dmin(db a, db b) 41 { 42     return a > b ? b : a; 43 } 44 db dmax(db a, db b) 45 { 46     return a > b ? a : b; 47 } 48 int sgn(db a) 49 { 50     return a < -eps ? -1 : a > eps;    //返回double型的符号 51 } 52  53 struct Point2D 54 { 55     db x, y; 56     int id; 57     Point2D(db _x = 0, db _y = 0): x(_x), y(_y) {} 58     void input() 59     { 60         scanf("%lf%lf" , &x, &y); 61     } 62     void output() 63     { 64         printf("%.2f %.2f\n" , x, y); 65     } 66     // 67     db len2() 68     { 69         return x * x + y * y; 70     } 71     //到原点距离 72     double len() 73     { 74         return sqrt(len2()); 75     } 76     //逆时针转90度 77     Point2D rotLeft90() 78     { 79         return Point2D(-y, x); 80     } 81     //顺时针转90度 82     Point2D rotRight90() 83     { 84         return Point2D(y, -x); 85     } 86     //绕原点逆时针旋转arc_u 87     Point2D rot(double arc_u) 88     { 89         return Point2D( x * cos(arc_u) - y * sin(arc_u), 90                         x * sin(arc_u) + y * cos(arc_u) ); 91     } 92     //绕某点逆时针旋转arc_u 93     Point2D rotByPoint(Point2D &center, db arc_u) 94     { 95         Point2D tmp( x - center.x, y - center.y ); 96         Point2D ans = tmp.rot(arc_u); 97         ans = ans + center; 98         return ans; 99     }100 101     bool operator == (const Point2D &t) const102     {103         return sgn(x - t.x) == 0 && sgn(y - t.y) == 0;104     }105     bool operator < (const Point2D &t) const106     {107         if ( sgn(x - t.x) == 0 ) return y < t.y;108         else return x < t.x;109     }110     Point2D operator + (const Point2D &t) const111     {112         return Point2D(x + t.x, y + t.y);113     }114 115     Point2D operator - (const Point2D &t) const116     {117         return Point2D(x - t.x, y - t.y);118     }119 120     Point2D operator * (const db &t)const121     {122         return Point2D( t * x, t * y );123     }124 125     Point2D operator / (const db &t) const126     {127         return Point2D( x / t, y / t );128     }129     //点乘130     db operator ^ (const Point2D &t) const131     {132         return x * t.x + y * t.y;133     }134     //叉乘135     db operator * (const Point2D &t) const136     {137         return x * t.y - y * t.x;138     }139     //两点之间的角度(-PI , PI]140     double rotArc(Point2D &t)141     {142         double perp_product = rotLeft90()^t;143         double dot_product = (*this)^t;144         if ( sgn(perp_product) == 0 && sgn(dot_product) == -1) return PI;145         return sgn(perp_product) * acos( dot_product / len() / t.len() );146     }147     //标准化148     Point2D normalize()149     {150         return Point2D(x / len(), y / len());151     }152 };153 154 struct POLYGON155 {156     Point2D v[POLYGON_MAX_POINT];157     int n;158 };159 struct Segment2D160 {161     Point2D s , e;162     Segment2D() {}163     Segment2D( Point2D _s, Point2D _e ): s(_s), e(_e) {}164 };165 //0: 点在多边形外166 //1: 点在多边形内167 bool PonSegment2D(Point2D p, Segment2D seg)168 {169     return sgn((seg.s - p) * (p - seg.e)) == 0 && sgn((seg.s - p) ^ (p - seg.e)) >= 0;170 }171 172 /**** 判断线段在内部相交***/173 bool SegIntersect2D(Segment2D a, Segment2D b)174 {175     //必须在线段内相交176     int d1 = sgn((a.e - a.s) * (b.s - a.s));177     int d2 = sgn((a.e - a.s) * (b.e - a.s));178     int d3 = sgn((b.e - b.s) * (a.s - b.s));179     int d4 = sgn((b.e - b.s) * (a.e - b.s));180     if (d1 * d2 < 0 && d3 * d4 < 0) return true;181     return false;182 }183 184 int PointInPolygon(Point2D p, Point2D poly[], int n)185 {186     Segment2D l, seg;187     l.s = p;188     l.e = p;189     l.e.x = INF;//作射线190     int i, cnt = 0;191     Point2D p1, p2, p3, p4;192     for (i = 0; i < n; i++)193     {194         seg.s = poly[i], seg.e = poly[(i + 1) % n];195         if (PonSegment2D(p, seg)) return 2; //点在多边形上196         p1 = seg.s, p2 = seg.e , p3 = poly[(i + 2) % n], p4 = poly[(i + 3) % n];197         if (SegIntersect2D(l, seg) ||198                 PonSegment2D(p2, l) && sgn((p2 - p1) * (p - p1))*sgn((p3 - p2) * (p - p2)) > 0 ||199                 PonSegment2D(p2, l) && PonSegment2D(p3, l) &&200                 sgn((p2 - p1) * (p - p1))*sgn((p4 - p3) * (p - p3)) > 0 )201             cnt++;202     }203     if (cnt % 2 == 1) return 1; //点在多边形内204     return 0;//点在多边形外205 }206 207 POLYGON poly;208 Point2D p, q;209 db a, b;210 void init()211 {212     //213 }214 void input()215 {216     scanf("%d%lf%lf", &poly.n, &a, &b);217     for (int i = 0; i < poly.n; i++)218     {219         scanf("%lf%lf", &poly.v[i].x, &poly.v[i].y);220     }221 }222 void debug()223 {224     //225 }226 void solve()227 {228     double ans = 0;229     for (int i = p.x; i <= q.x; i++)230     {231         for (int j = p.y; j <= q.y; j++)232         {233             if (PointInPolygon(Point2D(i, j), poly.v, poly.n))234                 ans += (a * i + b * j) * (min(i + 0.5, q.x) - max(i - 0.5, p.x)) * (min(j + 0.5, q.y) - max(j - 0.5, p.y));235         }236     }237     printf("%.3f\n", ans / (q.x - p.x) / (q.y - p.y));238 }239 void output()240 {241     //242 }243 int main()244 {245     // std::ios_base::sync_with_stdio(false);246     // #ifndef ONLINE_JUDGE247     //     freopen("in.cpp", "r", stdin);248     // #endif249 250     while (~scanf("%lf%lf%lf%lf", &p.x, &p.y, &q.x, &q.y))251     {252         init();253         input();254         solve();255         output();256     }257     return 0;258 }
View Code

 


联系
我们