Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 学习了pick

Posted by 731371663 at 2011-02-11 20:58:08 on Problem 1265
```//poj_1256 Area
//坐标图上的多边形，求多边形内部点数，边上点数，多边形面积。
//Pick公式：S=I+E/2-1，即多边形的面积=在多边形内的格点数+在多边形边上的格点数/2-1
//先用叉积求多变形面积，再根据公式计算内部点数量
//边界格点数---利用斜边对应的直角边的最大公约数

#include<iostream>
#include<cmath>
using namespace std;

int gcd(int a,int b)//最大公约数
{
while(b)
{
int temp=b;
b=a%b;
a=temp;
}
return a;
}

int get_area(int x1,int y1,int x2,int y2)//叉积求三角形面积
{
return (x1*y2-x2*y1);
}

int main()
{
//freopen("in.txt","r",stdin);
int i,t,n,area,in,on;
int x1,y1,x2,y2,x,y;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
x1=y1=0;
area=on=0;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&x,&y);
on+=gcd(abs(x),abs(y));//求边上点的个数
x2=x1+x;
y2=y1+y;
area+=get_area(x1,y1,x2,y2);
x1=x2;
y1=y2;
}
in=area/2-on/2+1;
printf("Scenario #%d:\n%d %d %.1lf\n\n",i,in,on,area/2.0);
}
return 0;
}

Followed by: