| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1136 人关注过本帖
标题:求助浙大ACM1739
只看楼主 加入收藏
HaPpY随心
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2007-9-28
收藏
 问题点数:0 回复次数:6 
求助浙大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;

}
}
搜索更多相关主题的帖子: area int polygon MAX define 
2008-01-21 15:52
HaPpY随心
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2007-9-28
收藏
得分:0 
想描出各个边界点,用求多边形面积法,求面积
边界点(除输入的)用两线段是否相交来判断
2008-01-21 15:55
HaPpY随心
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2007-9-28
收藏
得分:0 
想得复杂了,希望斑竹能帮我看看,谢谢
2008-01-21 15:57
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
能否将原题用中文简略描述一下

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-01-22 17:15
HaPpY随心
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2007-9-28
收藏
得分:0 
输入正整数N>=3,表示顶点数目,再输入N个顶点(都是整数)。
以X,Y坐标轴,将XOY平面分成单位面积为1的正方形(格子)
计算多边行包围的面积(也包括点和边所占的格子)
2008-01-23 16:35
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
"将XOY平面分成单位面积为1的正方形(格子)"
XOY平面是以X坐标 原点 和 Y坐标连接构成的三边形吗?

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-01-24 18:24
HaPpY随心
Rank: 1
等 级:新手上路
帖 子:119
专家分:0
注 册:2007-9-28
收藏
得分:0 
回复 6# 的帖子
不是,我想说算出的面积都是整数,按单位面积算
2008-01-26 14:01
快速回复:求助浙大ACM1739
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.086686 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved