SPOJ - AMR11B

题目链接:https://www.spoj.com/problems/AMR11B/en/

题目大意就是要你求图形覆盖的格点数,标记每个图形里的未标记格点(包括边界),总标记数就是覆盖的总格点数。

 #include<iostream>
#include<algorithm>
using namespace std;
struct node{
int x;
int y;
};
int t,n,visit[][];
void ri(node &a)//将每个点的横纵坐标加100
{
a.x+=;
a.y+=;
}
int po(node a,node b)//计算向量的点乘
{
return a.x*b.x+a.y*b.y;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
getchar();
for(int i=;i<;i++)
for(int j=;j<;j++)
visit[i][j]=;
while(n--)
{
char op[];
cin>>op;
if(op[]=='S')
{
node a;
int l;
cin>>a.x>>a.y>>l;
ri(a);
for(int i=a.x;i<=a.x+l;i++)
for(int j=a.y;j<=a.y+l;j++)
if(!visit[i][j])
visit[i][j]=;
}
else if(op[]=='C')
{
node a;
int r;
cin>>a.x>>a.y>>r;
ri(a);
for(int i=a.x-r;i<=a.x+r;i++)
for(int j=a.y-r;j<=a.y+r;j++)
if(!visit[i][j]&&(abs(a.x-i)*abs(a.x-i)+abs(a.y-j)*abs(a.y-j)<=r*r))
visit[i][j]=;
}
else
{//判断点是否在三角形内用到了斜面坐标系法,参考链接我会发到下面
node A,B,C,AC,AB;
cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y;
ri(A);ri(B);ri(C);
int x1,x2,y1,y2;
x1=min(A.x,min(B.x,C.x));x2=max(A.x,max(B.x,C.x));//锁定判断范围
y1=min(A.y,min(B.y,C.y));y2=max(A.y,max(B.y,C.y));
AC.x=C.x-A.x;AC.y=C.y-A.y;AB.x=B.x-A.x;AB.y=B.y-A.y;
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
if(!visit[i][j])
{
node P,AP;
P.x=i;P.y=j;
AP.x=P.x-A.x;AP.y=P.y-A.y;
int a=po(AP,AC),b=po(AB,AB),c=po(AP,AB),d=po(AC,AB),e=po(AC,AC),ans;
ans=(a*b-c*d)+(c*e-a*d)-(e*b-d*d);
if((a*b-c*d)>=&&(c*e-a*d)>=)
if(ans<=)
{
visit[i][j]=;
}
}
}
}
int ans=;
for(int i=;i<;i++)
for(int j=;j<;j++)
if(visit[i][j])
ans++;
cout<<ans<<endl;
}
return ;
}

判断点是否在三角形内:https://www.cnblogs.com/kyokuhuang/p/4314173.html

上一篇:Git 安装和使用教程


下一篇:hadoop更改保存路径后,批量重启不能启动datanode(或者format以后不能启动datanode)