• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            PKU2504 Rounding Box

            Posted on 2008-05-04 14:41 oyjpart 閱讀(2711) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            前幾天的練習賽有一道計算幾何題,一向討厭計算幾何的我推了一下之后就沒做了。
            后來比賽結束的時候發現他們都過了,后悔不已。故做了一下,求三角形外接圓圓心那個我使用
            垂直平分線相交的那個做的。上次他們說有公式,我在書上找了個圓心公式,可是代進去不對。
            估計是書上公式寫錯了...
             Bounding box
            Time Limit: 1.0 Seconds   Memory Limit: 65536K
            Total Runs: 28   Accepted Runs: 14    Multiple test files



            The Archeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at vertices of regular polygons. The moving sand dunes of the desert render the excavations difficult and thus once three vertices of a polygon are discovered there is a need to cover the entire polygon with protective fabric.

            Input contains multiple cases. Each case describes one polygon. It starts with an integer n ≤ 50, the number of vertices in the polygon, followed by three pairs of real numbers giving the x and y coordinates of three vertices of the polygon. The numbers are separated by whitespace. The input ends with a n equal 0, this case should not be processed.

            For each line of input, output one line in the format shown below, giving the smallest area of a rectangle which can cover all the vertices of the polygon and whose sides are parallel to the x and y axes.

            Sample input

            4
            10.00000 0.00000
            0.00000 -10.00000
            -10.00000 0.00000
            6
            22.23086 0.42320
            -4.87328 11.92822
            1.76914 27.57680
            23
            156.71567 -13.63236
            139.03195 -22.04236
            137.96925 -11.70517
            0

            Output for the sample input

            Polygon 1: 400.000
            Polygon 2: 1056.172
            Polygon 3: 397.673

            // solution by alpc12
            #include <cstdio>
            #include <cmath>

            const double EPS = 1e-8;
            const double PI = acos(-1.0);
            const double INF = 1e100;

            #define Min(a, b) (a<b?a:b)
            #define Max(a, b) (a>b?a:b)

            struct Point {
                double x;
                double y;
                Point() {}
                Point(double xx, double yy) {
                    x = xx;
                    y = yy;
                }
            };

            struct Line {
                double a, b, c;
                Point st, end;
                Line() {}
                Line(Point& u, Point& v) {
                    st = u;
                    end = v;
                    a = v.y - u.y;
                    b = u.x - v.x;
                    c = a*u.x + b*u.y;
                }
            };

            #define sqr(a) ((a)*(a))
            #define dist(a, b) (sqrt( sqr((a).x-(b).x)+sqr((a).y-(b).y) ))
            #define cross(a, b, c)  (((b).x-(a).x)*((c).y-(a).y)-((b).y-(a).y)*((c).x-(a).x))

            inline int dblcmp(double a, double b = 0.0) {
                if(fabs(a-b) < EPS) return 0;
                return a < b ? -1 : 1;
            }

            Line bisector(Point& a, Point& b) {
                Line line(a, b), ans;    
                double midx = (a.x+b.x)/2, midy = (a.y+b.y)/2;
                ans.a = -line.b, ans.b = line.a, ans.c = ans.a*midx + ans.b*midy;
                return ans;
            }

            int line_line_intersect(Line& l1, Line& l2, Point& s) {
                double det = l1.a * l2.b - l2.a * l1.b;
                if(dblcmp(det) == 0) {
                    return -1;
                }
                s.x = (l2.b*l1.c - l1.b*l2.c) / det;
                s.y = (l1.a*l2.c - l2.a*l1.c) / det;
                return 1;
            }

            int center_3point(Point& a, Point& b, Point& c, Point& s, double& r) {
                Line x = bisector(a, b), y = bisector(b, c);
                if(line_line_intersect(x, y, s) == 1) {
                    r = dist(s, a);
                    return 1;
                }
                return 0;
            }

            Point p[55];

            int main() {

                //freopen("t.in", "r", stdin);

                int i, n, tc = 0;
                Point cent;
                while(scanf("%d", &n), n) {
                    for(i = 0; i < 3; ++i) scanf("%lf %lf ", &p[i].x, &p[i].y);
                    double r;
                    if(center_3point(p[0], p[1], p[2], cent, r) == 1) {
                        for(i = 0; i < 3; ++i)
                            p[i].x -= cent.x, p[i].y -= cent.y;
                    }
                    double alpha = acos(p[0].x / r);
                    double theta = 2 * PI / n;
                    double xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
                    for(i = 0; i < n; ++i) {
                        p[i] = Point(r * cos(alpha + i * theta),
                            r * sin(alpha + i * theta));
                        xmin = Min(xmin, p[i].x);
                        xmax = Max(xmax, p[i].x);
                        ymin = Min(ymin, p[i].y);
                        ymax = Max(ymax, p[i].y);
                    }
                    printf("Polygon %d: %.3lf\n", ++tc, (xmax-xmin)*(ymax-ymin));
                }
                return 0;
            }

            Feedback

            # re: PKU2504 Rounding Box  回復  更多評論   

            2008-05-05 09:02 by oyjpart
            那個大牛給我個正確的求圓心的坐標的公式?

            # re: PKU2504 Rounding Box  回復  更多評論   

            2008-05-05 12:21 by alpc55
            @oyjpart
            想要嗎~~~
            我有哈~~~

            # re: PKU2504 Rounding Box  回復  更多評論   

            2008-05-05 14:35 by oyjpart
            謝謝啊
            热久久视久久精品18| 久久人人爽人人爽人人片av高请 | 久久精品国产亚洲精品2020 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久天天躁狠狠躁夜夜av浪潮| 97久久婷婷五月综合色d啪蜜芽| 国产精品VIDEOSSEX久久发布| 欧美成a人片免费看久久| 久久久久高潮综合影院| 欧美午夜A∨大片久久| 日本免费久久久久久久网站| 亚洲va国产va天堂va久久| 日本WV一本一道久久香蕉| 久久亚洲国产精品五月天婷| 亚洲AV日韩精品久久久久久久 | 亚洲国产成人精品91久久久| 伊人久久精品无码二区麻豆| 伊人久久免费视频| 久久这里只精品国产99热| 亚洲国产成人乱码精品女人久久久不卡 | 大香网伊人久久综合网2020| 99久久国产宗和精品1上映| 国产亚州精品女人久久久久久 | 久久久无码精品午夜| 久久久久女人精品毛片| 亚洲国产日韩欧美久久| 97精品伊人久久久大香线蕉| 久久99精品久久只有精品| 久久er99热精品一区二区| 久久只有这精品99| 亚洲&#228;v永久无码精品天堂久久 | 一级做a爰片久久毛片免费陪 | 97久久国产综合精品女不卡 | 99国产欧美久久久精品蜜芽| 国产精品一区二区久久不卡| 久久午夜福利无码1000合集| 久久久久女教师免费一区| 久久国产色av免费看| 亚洲精品WWW久久久久久| 国产免费久久精品丫丫| 青青草国产精品久久|