• <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>

            ZOJ 1032 Area 2

            Area 2

            Time limit: 1 Seconds   Memory limit: 32768K  
            Total Submit: 735   Accepted Submit: 317  

            Background

            Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new research and development facility the company has installed the latest system of surveillance robots patrolling the area. These robots move along the walls of the facility and report suspicious observations to the central security office. The only flaw in the system a competitor’s agent could find is the fact that the robots radio their movements unencrypted. Not being able to find out more, the agent wants to use that information to calculate the exact size of the area occupied by the new facility. It is public knowledge that all the corners of the building are situated on a rectangular grid and that only straight walls are used. Figure 1 shows the course of a robot around an example area.

            Figure 1: Example area.

            Problem

            You are hired to write a program that calculates the area occupied by the new facility from the movements of a robot along its walls. You can assume that this area is a polygon with corners on a rectangular grid. However, your boss insists that you use a formula he is so proud to have found somewhere. The formula relates the number I of grid points inside the polygon, the number E of grid points on the edges, and the total area A of the polygon. Unfortunately, you have lost the sheet on which he had written down that simple formula for you, so your first task is to find the formula yourself.


            Input

            The first line contains the number of scenarios.

            For each scenario, you are given the number m, 3<=m<100, of movements of the robot in the first line. The following m lines contain pairs “dx dy” of integers, separated by a single blank, satisfying .-100<=dx, dy<=100 and (dx, dy)!=(0, 0). Such a pair means that the robot moves on to a grid point dx units to the right and dy units upwards on the grid (with respect to the current position). You can assume that the curve along which the robot moves is closed and that it does not intersect or even touch itself except for the start and end points. The robot moves anti-clockwise around the building, so the area to be calculated lies to the left of the curve. It is known in advance that the whole polygon would fit into a square on the grid with a side length of 100 units.


            Output

            The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing I, E, and A, the area A rounded to one digit after the decimal point. Separate the three numbers by two single blanks. Terminate the output for the scenario with a blank line.


            Sample Input

            2
            4
            1 0
            0 1
            -1 0
            0 -1
            7
            5 0
            1 3
            -2 2
            -1 0
            0 -3
            -3 1
            0 -3


            Sample Output

            Scenario #1:
            0 4 1.0

            Scenario #2:
            12 16 19.0


            Problem Source: Northwestern Europe 2001

             Analysis
            Algorithm:
            It is a basic computational geometry problem. For the task, the description aims us to calculate the points inner and on edge. But we can measure the area by the vector formular:
            (P.S: the n+1 point is actually the first one,so  .)
            Later, using the pick formulat to calculate the inner points, while the points on the edge can be counted with the move vector, which is proved to be as same as the number of  .

            Code:
            #include <iostream>
            using namespace std;
            struct delta{
                
            int dx;
                
            int dy;
            }
            ;
            delta move[
            101];

            int gcd(int a,int b){
                
            if (a==0return b;
                
            if (b==0return a;
                
            return gcd(b,a%b);
            }

            int abs(int a){
                
            return a>0?a:-1*a;
            }

            int main(){
                
            int Scenario,s;
                cin
            >>s;
                
            for (Scenario=1;Scenario<=s;Scenario++){
                    
            int I=0,E=0,area=0;
                    
            int m;
                    cin
            >>m;
                    move[
            0].dx=0;
                    move[
            0].dy=0;
                    
            for (int i=1;i<=m;i++){
                        cin
            >>move[i].dx>>move[i].dy;
                        E
            +=gcd(abs(move[i].dx),abs(move[i].dy));
                        move[i].dx
            +=move[i-1].dx;
                        move[i].dy
            +=move[i-1].dy;
                    }

                    
            for (i=1;i<m-1;i++){
                        area
            +=move[i].dx*move[i+1].dy-move[i].dy*move[i+1].dx;
                    }

                    area
            =abs(area);
                    I
            =(area+2-E)/2;
                    cout
            <<"Scenario #"<<Scenario<<":"<<endl;
                    cout
            <<I<<" "<<E<<" ";
                    
            if (area%2) cout<<area/2+0.5<<endl;
                    
            else cout<<area/2<<".0"<<endl;
                    cout 
            <<endl;
                    
            for (i=1;i<=m;i++){
                        move[i].dx
            =0;
                        move[i].dy
            =0;
                    }

                }

                
            return 0;
            }

            posted on 2008-08-09 19:02 幻浪天空領主 閱讀(508) 評論(0)  編輯 收藏 引用 所屬分類: ZOJ

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品成人久久久久久久| 四虎影视久久久免费| 97久久婷婷五月综合色d啪蜜芽| 亚洲欧美日韩精品久久亚洲区| 久久天天躁狠狠躁夜夜躁2014| 综合久久给合久久狠狠狠97色| 伊人久久大香线蕉综合Av| 婷婷久久香蕉五月综合加勒比| 精品久久一区二区三区| 久久久久久亚洲精品无码| 久久免费看黄a级毛片| 97精品久久天干天天天按摩| 欧美性大战久久久久久| 久久婷婷五月综合97色一本一本| 国产高潮久久免费观看| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 久久人人添人人爽添人人片牛牛| 97久久久久人妻精品专区| 欧美亚洲日本久久精品| 国产精品视频久久| 久久亚洲精品无码VA大香大香 | 91久久精品国产91性色也| 久久午夜夜伦鲁鲁片免费无码影视| 久久精品国产福利国产秒| 欧美日韩精品久久久久| 激情综合色综合久久综合| 狠狠色婷婷久久一区二区三区| 99精品国产综合久久久久五月天| 久久综合久久鬼色| 久久国产视屏| 久久精品国产99久久久香蕉| 久久精品视频网| 久久精品一区二区国产| 国产精品久久一区二区三区| 99久久久国产精品免费无卡顿| 日韩精品久久无码中文字幕| 亚洲va久久久噜噜噜久久| 久久精品青青草原伊人| 国产69精品久久久久观看软件| 少妇熟女久久综合网色欲| 伊人久久成人成综合网222|