500MS弄到79MS，求多邊形面積，有可能是凹，用叉積就可以了，不能存所有點，會MLE
一次讀入比單個讀入快
#include<iostream>
#include<math.h>
using namespace std;
struct point 
{__int64 x,y;};
__int64 dx[]={0,-1,0,1,-1,0,1,-1,0,1};
__int64 dy[]={0,-1,-1,-1,0,0,0,1,1,1};
//__int64 xmult(point p0,point p1,point p2){
// return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
//}
char path[1000010];
int main()
{
int t;
point p0,p1,p2;
__int64 ans;
scanf("%d",&t);
while(t--)
{
p0.x=0;
p0.y=0;
p2=p1=p0;
ans=0;
scanf(" %s",path);
int i=0;
for(i=0;path[i]!='5';i++)
{
p1=p2;
p2.x+=dx[path[i]-'0'];
p2.y+=dy[path[i]-'0'];
ans+=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
if(ans<0) ans*=-1;
printf("%I64d",(ans>>1));
if(((ans>>1)<<1)==ans) printf("\n");
else printf(".5\n");
}
return 0;
}
posted on 2009-10-06 13:12
wyiu 閱讀(137)
評論(0) 編輯 收藏 引用 所屬分類:
POJ