求助浙大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;
}
}
