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

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产精品无码久久| 久久天天躁狠狠躁夜夜avapp| 精品免费tv久久久久久久| 国产精品久久久久国产A级| 99麻豆久久久国产精品免费| 麻豆精品久久久一区二区| 久久久久九九精品影院| 亚洲第一极品精品无码久久| 久久综合九色综合97_久久久| 精品久久久久久无码中文野结衣| 精品国产乱码久久久久软件| 久久er热视频在这里精品| 久久这里的只有是精品23| 日日噜噜夜夜狠狠久久丁香五月 | 亚洲国产综合久久天堂| 无码久久精品国产亚洲Av影片| 777米奇久久最新地址| 久久婷婷五月综合色99啪ak| 久久婷婷五月综合97色| 伊人久久大香线蕉综合5g| 久久99精品国产| 性欧美大战久久久久久久久 | 久久久久国产精品人妻| 99久久精品无码一区二区毛片| 国产成人精品久久| 人妻丰满?V无码久久不卡| 国产精品久久久久影院嫩草| 一本一本久久A久久综合精品| 无码人妻少妇久久中文字幕| 久久精品成人国产午夜| 久久久久成人精品无码中文字幕 | 99精品久久精品| 精品久久人妻av中文字幕| 东方aⅴ免费观看久久av| 久久无码精品一区二区三区| 久久久久久久综合日本| 一本色道久久88加勒比—综合| 久久96国产精品久久久| 久久免费视频网站| 人人狠狠综合久久亚洲婷婷| 色综合久久88色综合天天|