求助浙大ACM1739(页 1) - 数据结构与算法

HaPpY随心 发表于 2008-1-21 15:52

求助浙大ACM1739

#include <iostream>
using namespace std;
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)

typedef struct
{
int x,y;
}Point;

int  polygonarea(Point *polygon,int N)
{
int i,j;
int area = 0;
    for (i=0;i<N;i++)
      {
            j = (i + 1) % N;
            area += polygon[i].x * polygon[j].y;
            area -= polygon[i].y * polygon[j].x;
}
   area /= 2;
   return(area < 0 ? -area : area);
}
int lineintersect(Point p1,Point p2,Point p3,Point p4)
   {
      Point tp1,tp2,tp3;
      if
   ((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)||(p2.x==p4.x&&p2.y==p4.y))
            return 2;
   //快速排斥试验
      if
   ((MIN(p1.x,p2.x)<=p3.x&&p3.x<=MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<=p3.y&&p3.y<=MAX(p1.y,p2.y))||

   (MIN(p1.x,p2.x)<=p4.x&&p4.x<=MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<=p4.y&&p4.y<=MAX(p1.y,p2.y)))
            ;else return 0;
   //跨立试验
      tp1.x=p1.x-p3.x;
      tp1.y=p1.y-p3.y;
      tp2.x=p4.x-p3.x;
      tp2.y=p4.y-p3.y;
      tp3.x=p2.x-p3.x;
      tp3.y=p2.y-p3.y;
      if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0) return 1;
   else return 0;
   }

main()
{
Point vertex[100],a[1000],p,q;
int m,i,j,k;
while(cin>>m&&m>=3)
{
for(i=0;i<m;i++)
{
cin>>vertex[i].x>>vertex[i].y;
}
j=0;
for(i=0;i<m;i++)
{
a[j]=vertex[i];
j++;
if((vertex[i].x-vertex[i+1].x)==0||(vertex[i].y-vertex[i+1].y)==0)
continue;
if(vertex[i+1].x>vertex[i].x&&vertex[i+1].y<vertex[i].y)
{p.x=vertex[i].x+1;p.y=vertex[i].y;}
if(vertex[i+1].x<vertex[i].x&&vertex[i+1].y>vertex[i].y)
{p.x=vertex[i].x-1;p.y=vertex[i].y;}
if(vertex[i+1].x>vertex[i].x&&vertex[i+1].y>vertex[i].y)
{p.y=vertex[i].y+1;p.x=vertex[i].x;}
if(vertex[i+1].x<vertex[i].x&&vertex[i+1].y<vertex[i].y)
{p.y=vertex[i].y-1;p.x=vertex[i].x;}
k=0;
while(!k)
{
if(vertex[i+1].x>vertex[i].x&&vertex[i+1].y<vertex[i].y)
{
q.x=p.x-1;
q.y=p.y-1;
if((p.x==vertex[(i+1)%m].x)&&(p.y==vertex[(i+1)%m].y)) break;
k=lineintersect(vertex[i],vertex[i+1],p,q);
if(k!=0)
{a[j]=p;p.x++;j++;continue;}
else
p=q;
}
if(vertex[i+1].x<vertex[i].x&&vertex[i+1].y>vertex[i].y||vertex[i+1].x<vertex[i].x&&vertex[i+1].y<vertex[i].y)
{
q.x=p.x+1;
q.y=p.y+1;
k=lineintersect(vertex[i],vertex[i+1],p,q);
if((p.x==vertex[(i+1)%m].x)&&(p.y==vertex[(i+1)%m].y)) break;
if(k!=0)
{a[j]=p;p.x--;j++;continue;}
else p=q;
}
if(vertex[i+1].x>vertex[i].x&&vertex[i+1].y>vertex[i].y)
{
q.x=p.x-1;
q.y=p.y-1;
if((p.x==vertex[(i+1)%m].x)&&(p.y==vertex[(i+1)%m].y)) break;
k=lineintersect(vertex[i],vertex[i+1],p,q);
if(k!=0)
{a[j]=p;p.y++;j++;continue;}
else
p=q;
}
if(vertex[i+1].x<vertex[i].x&&vertex[i+1].y<vertex[i].y)
{
q.x=p.x+1;
q.y=p.y+1;
k=lineintersect(vertex[i],vertex[i+1],p,q);
if((p.x==vertex[(i+1)%m].x)&&(p.y==vertex[(i+1)%m].y)) break;
if(k!=0)
{a[j]=p;p.y--;j++;continue;}
else p=q;
}
}
}
cout<<(polygonarea(a,j))<<endl;

}
}

HaPpY随心 发表于 2008-1-21 15:55

想描出各个边界点，用求多边形面积法，求面积
边界点（除输入的）用两线段是否相交来判断

HaPpY随心 发表于 2008-1-21 15:57

想得复杂了，希望斑竹能帮我看看，谢谢

卧龙孔明 发表于 2008-1-22 17:15

能否将原题用中文简略描述一下

HaPpY随心 发表于 2008-1-23 16:35

输入正整数N>=3，表示顶点数目，再输入N个顶点（都是整数）。
以X，Y坐标轴，将XOY平面分成单位面积为1的正方形（格子）
计算多边行包围的面积（也包括点和边所占的格子）

卧龙孔明 发表于 2008-1-24 18:24

"将XOY平面分成单位面积为1的正方形（格子）"
XOY平面是以X坐标原点和 Y坐标连接构成的三边形吗?

HaPpY随心 发表于 2008-1-26 14:01

回复 6# 的帖子

不是，我想说算出的面积都是整数，按单位面积算

页: [1]