Area
Time Limit:1000MS |
|
Memory Limit:10000K |
Total Submissions:9899 |
|
Accepted:2800 |
Description
You are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex.
For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2.
For example, this is a legal polygon to be computed and its area is 2.5:
Input
The first line of input is an integer t (1 <= t <= 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North,
South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the
endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.
Output
For each polygon, print its area on a single line.
Sample Input
4
5
825
6725
6244865
Sample Output
0
0
0.5
2
前段时间一直在学java ,算法的进度 没跟上。 今天 做了 两道 计算几何的基础题。 这两天好好看看计算几何。 。
这题的思路: 用 向量的叉积 ( 有向面积 )。。 计算几何主要是 数学问题。
//Memory: 1172 KB Time: 32 MS
//Language: G++ Result: Accepted
#include<stdio.h>
#include<string.h>
char a[1000100];
struct point
{
int x,y;
}p1,p2;
int main()
{
int n,i,len;
long long int tempArea,area;
int dir[9][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{0,0},{1,0},{-1,1},{0,1},{1,1}};
while(scanf("%d%*c",&n)!=EOF)
{
p1.x=0;
p1.y=0;
while(n--)
{
tempArea=0;
gets(a);
len=strlen(a);
for(i=0;i<len;i++)
{
int d=a[i]-'1';
p2.x = p1.x + dir[d][0];
p2.y = p1.y + dir[d][1];
tempArea += p1.x * p2.y - p1.y * p2.x;
p1.x=p2.x;
p1.y=p2.y;
}
area=tempArea/2;
if(area<0) area*=-1;
printf("%lld",area);
if(tempArea%2!=0) printf(".5");
printf("\n");
}
}
return 0;
}
Disqus
Like
Dislike
分享到:
相关推荐
POJ3211--Washing Clothes
POJ水题集-----50道左右-----增加自信啊..
北大POJ初级-计算几何学 解题报告+AC代码
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ初级题-数据结构:解题报告+AC代码
POJ3259--Wormholes,使用bellman方法。
poj题目分类--acmer做题极有用资源
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
北大POJ3414-Pots 解题报告+AC代码
poj 2827 Auto-Calculation Machine.md
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj 1654的代码,供大家参考,看有没有更好的方法
用Java代码实现POJ(PKU)上题2494!
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...