精华内容
下载资源
问答
  • poj1265 皮克公式 求多边形面积(凹凸)
    2020-11-06 21:05:59

    题意

    一机器人从原点出发进行n 次移动,每次向右移动dxi​,向上移动dyi​,求画成的多边形内部有多少格点,边界上有多少格点,及其面积多大?

    皮克公式:S = 内部点 + 边界点/2 - 1;

    求出多边形面积(叉积),gcd求出边界点,皮克公式推内部点。

    顺便一提 这题不知道为啥 poj又是交G++wa C++AC……

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    
    using namespace std;
    const double eps = 1e-8;
    const double pi = acos(-1.0);
    const int MaxN = 1e6 + 5;
    typedef long long LL;
    
    int n,t;
    int dx[10] = {0,-1,0,1,-1,0,1,-1,0,1};
    int dy[10] = {0,-1,-1,-1,0,0,0,1,1,1};
    char s[MaxN];
    
    int gcd(int a,int b){
    	if(b == 0) return a;
    	return gcd(b,a % b);
    }
    
    struct Point{
    	int x,y;
    	Point(int x = 0,int y = 0) : x(x),y(y){}
    }p[MaxN];
    typedef Point Vector;
    
    int Cross(Vector A,Vector B){ return A.x * B.y - A.y * B.x;}
    
    int main(){
    	scanf("%d",&t);
    	for(int T = 1;T <= t; T++){
    		int E = 0,S = 0,ans = 0;
    		scanf("%d",&n);
    		for(int i = 1;i <= n; i++){
    			scanf("%d %d",&p[i].x,&p[i].y);
    		}
    		Point P,Pt;
    		P.x = 0,P.y = 0;
    		Pt.x = 0,Pt.y = 0;
    		for(int i = 1;i <= n; i++){
    			Pt.x = P.x + p[i].x;
    			Pt.y = P.y + p[i].y;
    			ans += Cross(Pt,P);
    			E += gcd(abs(P.x - Pt.x),abs(P.y - Pt.y));
    			P = Pt;
    		}
    		if(ans < 0) ans *= -1;
    		int In = (ans + 2 - E) / 2;
    		printf("Scenario #%d:\n",T);
    		double Ans = 1.0 * ans / 2.0;
    		printf("%d %d %.1f\n\n",In,E,Ans);
    	}
    	return 0;
    }

     

    更多相关内容
  • 皮克公式 Peake’s theorem 皮克公式是奥地利数学家皮克发现的一个计算点阵中多边形的面积公式. 简单说就是在一个坐标纸、表格纸、点阵纸上,有一个所有顶点都在点上的多边形,那么这个多边形的面积满足: 其中n...

    皮克公式 Peake’s theorem

    皮克公式是奥地利数学家皮克发现的一个计算点阵中多边形的面积公式.

    简单说就是在一个坐标纸、表格纸、点阵纸上,有一个所有顶点都在点上的多边形,那么这个多边形的面积满足:

    在这里插入图片描述
    其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积
    例如:
    在这里插入图片描述

    展开全文
  • 要用到皮克公式 Pick公式:平面上以格子点为顶点的简单多边形的 面积 = 边上的点数/2+内部的点数-1。 任意一个多边形的面积等于 :按顺序 求相邻两个点与原点组成的向量的叉积之和/2(可以利用三角形求证,需要...

    Area

    Time Limit: 1000MS Memory Limit: 10000K
    Total Submissions: 7355 Accepted: 3124

    Description

    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抯 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. 


    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 揹x 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 揝cenario #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

    Source

    Northwestern Europe 2001

    [Submit]   [Go Back]   [Status]   [Discuss]

    Home Page   Go Back  To top


    All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
    Any problem, Please Contact Administrator

    这道题让你求的是多边形边界,内部有几个点以及多边形的面积。要用到皮克公式

    Pick公式:平面上以格子点为顶点的简单多边形的 面积 = 边上的点数/2+内部的点数-1。

    任意一个多边形的面积等于 :按顺序 求相邻两个点与原点组成的向量的叉积之和/2(可以利用三角形求证,需要取绝对值 二维叉积公式:x1y2-x2y1)。这里面我们可以把原点设置为0。0点。

    以格子点为顶点的线段,其覆盖的点的个数为GCD(dx,dy),dxdy分别为线段横向坐标差值和纵向差值。如果dx或dy为0,则覆盖的点数为dy或dx(此时平行于坐标轴)。
    注意这道题里面输入的是dx,dy不是每一个点的坐标,而是沿着x轴,y轴方向走了多少步。所以要想办法把每一个点的坐标求出来,可以通过每一步走步和前一个点想加来求出点的坐标。

    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXN=10005;
    int n;
    struct Line{
        int x,y;
    }line[MAXN];
    int det(Line l1,Line l2){
        return l1.x*l2.y-l2.x*l1.y;
    }
    int gcd(int a,int b){
        if(b==0) return a;
        else return gcd(b,a%b);
    }
    double poloygonArea(Line* l,int n){
        double area;
        for(int i=2;i<=n;i++){
            area=area+det(l[i],l[i-1]);
        }
        return fabs(area/2);
    }
    int main(){
        int t;
        cin>>t;
        int kase=0;
        while(t--){
            cin>>n;
            double ans=0;//计算多边形内部的格点数
            for(int i=1;i<=n;i++){
                scanf("%d%d",&line[i].x,&line[i].y);
                ans=ans+gcd(abs(line[i].x),abs(line[i].y));
                line[0].x=0;
                line[0].y=0;
                line[i].x=line[i].x+line[i-1].x;
                line[i].y=line[i].y+line[i-1].y;
            }
            double area=poloygonArea(line,n);
            double edge=area+1-ans/2;
            printf("Scenario #%d:\n",++kase);
            printf("%d %d %.1lf\n",(int)edge,(int)ans,area);
            printf("\n");
        }
        return 0;
    }
    

     

    展开全文
  • 链接:https://www.nowcoder.net/acm/contest/75/I来源:牛客网时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld题目描述 给你一个三角形的顶点A,B,C的坐标(坐标都...

    链接:https://www.nowcoder.net/acm/contest/75/I
    来源:牛客网

    时间限制:C/C++ 1秒,其他语言2秒
    空间限制:C/C++ 32768K,其他语言65536K
    64bit IO Format: %lld

    题目描述

     

    给你一个三角形的顶点A,B,C的坐标(坐标都为整数),请求出三角形的面积,三角形内的点的个数以及边AB、BC和AC边上的点的个数(不包括顶点ABC)

    输入描述:

    多组输入
    每组输入三行,每行两个整数
    第一行顶点A的坐标Xa,Ya.
    第二行顶点B的坐标Xb,Yb.
    第三行顶点C的坐标Xc,Yc.
    0<=X,Y<=1,000,000
    输入-1结束输入

    输出描述:

    每组输出一行,输出一个实数(保留一位小数),四个整数,分别代表三角形面积,三角形内的点的个数以及边AB、BC和AC边上的点的个数,每个数用空格隔开。

    #include <iostream> 
    #include <stdio.h> 
    #include <string.h> 
    #include <algorithm> 
    #include <math.h> 
    using namespace std;
    #define LL long long 
    long long int gcd(long long int a, long long int b)
    {
        //cout << a << " x " << b << endl;
        if (b == 0)
        {
            return a;
        }
        else
        {
            return gcd(b, a%b);
        }
    }
    int main()
    {
        long long int x[3], y[3];
        while (cin >> x[0] && x[0] != -1)
        {
            cin >> y[0];
            for (int s = 1; s <= 2; s++)
            {
                cin >> x[s] >> y[s];
            }
            long long int bian = gcd(fabs(x[0] - x[1]), fabs(y[0] - y[1])) + gcd(fabs(x[1] - x[2]), fabs(y[1] - y[2])) + gcd(fabs(x[2] - x[0]), fabs(y[2] - y[0]));
            //s=a+b/2-1;
            //cout << bian << endl;
            double s = fabs((x[0] * y[1] + x[1] * y[2] + x[2] * y[0] - x[0] * y[2] - x[1] * y[0] - x[2] * y[1])) / 2;
            long long int neibu = (s + 1 - bian / 2);
            printf("%.1lf %lld %lld %lld %lld\n", s, neibu, gcd(fabs(x[0] - x[1]), fabs(y[0] - y[1]))-1, gcd(fabs(x[1] - x[2]), fabs(y[1] - y[2]))-1, gcd(fabs(x[2] - x[0]), fabs(y[2] - y[0]))-1);
        }
        return 0;
    }
    

    展开全文
  • 皮克公式:S = a+b/2-1,其中a表示多边形内部的点数,b表示多边形边界上的点数,s表示多边形的面积 多边形面积求法: http://blog.csdn.net/jaihk662/article/details/51784898 #include #...
  • 皮克公式:设面积为S,多边形内的点数为I,多边形边上的点数为B,那么:S=I+B2−1使用要求:\\ 必须是点阵中,选取的都是整数点。\\ 皮克公式:\\ 设面积为S,多边形内的点数为I,多边形边上的点数为B,那么:\\ S=I...
  • 皮克定理和任意多边形的面积公式

    千次阅读 2018-11-09 19:19:19
    2.皮克公式: 即:多边形面积 S = 多边形内整数点的个数 n + 多边形边上整数点的个数 / 2 -1 注:多边形的顶点坐标必须是整数 3. 线段上整数点的个数: gcd(线段在x轴的投影长,线段在y轴的投影长) + 1 ...
  • 均是整点(或正方形格点)的简单多边形,皮克定理说明了其面积S和内部格点数目n、边上格点数目s的关系: (其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积) #include ...
  • 皮克公式:S=A+B/2−1S=A+B/2−1S = A+B/2-1,其中A表示多边形内部的点数,B表示多边形边界上的点数,S表示多边形的面积,用gcd求边界点数。求面积我用海伦公式,精度给挂了. #include &lt;cstdio&gt; #...
  • 题意:一机器人从原点出发进行nnn次移动,每次向右移动dxidx_idxi​,向上...Pick公式 对于顶点坐标均为整数的简单多边形: 面积=内部格点数目+边界格点数目/2−1面积=内部格点数目+边界格点数目/2-1面积=内部格点数...
  • 皮克公式:求格点多边形面积 A=B2+I−1 A=\frac B 2+I-1 A=2B​+I−1 其中 A:area 面积 B:boundary 边界上整点的个数 I:interior 多边形内部点的个数 对于两个整数点(x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)(x1​,y1...
  • 皮克公式: \[S = \frac{i}{2}+b-1\] \(S\)为三角形面积,\(i\)为三角形边界上的格点个数,\(b\)为三角形内部的格点个数。 \(i\)可由\(gcd\)求得。 Code #include <bits/stdc++.h> usin...
  • 容斥定理,皮克公式

    2018-02-09 20:04:00
    (来源:哈工大算法培训) 容斥定理:在计算集合的...皮克公式: 1、如何求多边形面积: 例: 思路:按顺序两点求叉积。 S=abs(1/2*((x1*y2-x2*y1)+.......+(xk*yk+1-xk+1*yk)+.........+(xn*y1-x1*yn)...
  • 皮克定理: 设面积为S,I为多边形内整数点的数量,B为多边形边上整数点的数量, 那么有: S=I+B/2-1 由于给定点的坐标都是偶数, 可推出S也一定是偶数. 题目要求I是奇数, 我们只需要考虑奇偶性, 那么S,1,I都是已知的了. ...
  •   题意: 在x [0,n]. y[0,m]的坐标系中,找到一个格点...皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为2S=2a+b-2,其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多...
  • 浅谈皮克定理

    千次阅读 2018-11-18 23:54:00
    皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式皮克定理:S=a+b2−1 皮克定理:S = a + \frac{b}{2} -1 皮克定理:S=a+2b​−1 S表示多边形的面积 a表示多边形内的整数点 b表示多边形边界上的整数点 ...
  • 匹克公式: #include #include #include using namespace std; #define ll long long int main(void) { ll x,y,xx,yy,n,m; double s1,s2; while(scanf("%lld%lld",&n,&m)!=EOF) { scanf("%lld%lld%lld...
  • 1,皮克公式: S = 1/2×(( X1*Y2-X2*Y1) + … + (Xk*Yk+1-Xk+1*Yk )+ ... +( Xn*Y1-X1*Yn )) 用于求多边形的面积 需要注意的是,如果一系列点按逆时针排列算出的是正面积,而如果是顺时针的话算出的则是一个负...
  • 皮克定理(计算多边形面积)

    千次阅读 2018-06-03 11:08:42
    皮克定理:用于计算点阵中顶点在格点上的多边形的面积;公式表达为2S= 2a + b - 2.S表示多边形的面积,a表示多边形内部的点数,b表示多边形边界上的点数。假设有一个直角三角形,它的两条直角边上的点数分别为x、y,...
  • 皮克定理求格点

    2018-11-27 23:16:16
    皮克定理 一张方格纸上,上面画着纵横两组平行线,相邻平行线之间的距离都相等,这样两组平行线的交点,就是所谓格点。如果取一个格点做原点O,如图1,取通过这个格点的横向和纵向两直线分别做横坐标轴OX和纵坐标轴...
  • ( 算法树之几何 )【 皮克定理 】 皮克定理是有关格点多边形的面积计算问题,因此在了解皮克定理前,我们要先看一下什么是格点...1899年,奥地利数学家乔治亚历山大匹克对格点多边形面积计算问题给出了以下公式...
  • “数格点算面积”

    2021-02-12 05:23:29
    (2)如果每相邻的三个点构成的小等边三角形的面积是1(如图6),那么还能用“皮克公式”来求多边形的面积吗? 设计意图:让学生带着问题走出课堂,能尝试运用本节课解决问题的思想方法去解决类似的问题,进一步...
  • 皮克定理 一个多边形的顶点如果全是格点,这多边形就叫做格点多边形。有趣的是, 这种格点多边形的面积计算起来很方便...这个公式皮克(pick)在1899年给出的,被称为“皮克定理”,这是一 个实用而又有趣的定理。
  • 皮克定理

    千次阅读 2020-02-03 15:53:40
    皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为2S=2a+b-2,其中a表示多边形内部的点数,b表示多边形落在格点边界上的点数,S表示多边形的面积。 上图中红色点数为a,蓝色点数为b 可得...
  • 由pick定理得: a=s-b/2+1 所以第一个未知数 b可以求,第二个s也可以求 套用多边形面积公式: s=1/2(x1*y2-x2*y1+x2*y3-x3*y2~~~~~~) 即可得出: #include #define E 2.718 using namespace std; typedef long long ll;...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 272
精华内容 108
关键字:

皮克公式