zoj 1010 area 问题求解
问题在http://acm.zju.edu.cn/show_problem.php?pid=1010
这是我写的代码
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double max(double a,double b){
return a> b?a:b;
}
double min(double a,double b){
return a <=b?a:b;
}
class Point{
public:
double x;
double y;
};
double mulity(Point a,Point b,Point o){ //叉积
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double pointinline(Point a,Point b,Point o1,Point o2){//判断两不相领线段是否相交
return( (max(a.x,b.x)> =min(o1.x,o2.x))&&
(max(o1.x,o2.x)> =min(a.x,b.x))&&
(max(a.y,b.y)> =min(o1.y,o2.y))&&
(max(o1.y,o2.y)> =min(a.y,b.y))&&
(mulity(o1,b,a)*mulity(o2,b,a) <=0)&&
(mulity(a,o2,o1)*mulity(b,o2,o1) <=0)); //1的话相交；
}
int mulityline(Point *a,int num){ //判断多边形相交
int k;
for(int i=3;i <num;i++){ //判断不相领的线段是否相交
for(int j=1;j <i-1;j++){
if(pointinline(a[j],a[j-1],a[i],a[i-1])){
return 0; //相交
}
}
}
for(k=2;k <num;k++) //相邻的线段是否相交
if(!mulity(a[k-2],a[k-1],a[k])&&a[k].x> =min(a[k-2].x,a[k-1].x)&&a[k].x <=max(a[k-2].x,a[k-1].x)
&&a[k].y> =min(a[k-2].y,a[k-1].y)&&a[k].y <=max(a[k-2].y,a[k-1].y))
return 0;//相交
for(int j=2;j <num-2;j++){
if(pointinline(a[j],a[j-1],a[0],a[num-1]))
return 0;
}
return 1; //不相交
}
double area(Point *a,int num){ //计算多边形的面积
double sum=0;
int i;
for(i=0;i <num-1;i++)
sum+=(a[i].x*a[i+1].y-a[i].y*a[i+1].x);
sum+=(a[0].x*a[num-1].y-a[num-1].x*a[0].x);
sum/=2;
return fabs(sum);
}
int main(){
cout.setf(ios::fixed);
cout.precision(2);
Point p[1000];
double ans[1000]={0};
int j=0,i=0;
int num;
while(cin> > num){
if(!num)
break;
if(num <3){
ans[j]=0;
j++;
}
for(i=0;i <num;i++){
cin> > p[i].x> > p[i].y;
}
if(mulityline(p,num)){
ans[j]=area(p,num);
j++;
}
else{
ans[j]=0;
j++;
}
}
for(int k=0;k <j;k++){
cout.setf(ios::fixed);
cout.precision(2);
cout < < "Figure " < <k+1 < < ": ";
if(ans[k]!=0){
cout.setf(ios::fixed);
cout.precision(2);
cout < <ans[k] < <endl;
}
else if(ans[k]==0)
cout < < "Impossible " < <endl;
}
}
谁能帮帮我啊，不然饭都吃不进了，老是WA。
[解决办法]
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
#define infinity 1e20
#define EP 1e-10
#define float double
struct TPoint{
float x,y;
};
struct TLineSeg{
TPoint a,b;
};
double max(double a,double b)
{
if(a> b)
return a;
else
return b;
}
double min(double a,double b)
{
return a+b-max(a,b);
}
float distance(TPoint p1,TPoint p2)
{
return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
float multiply(TPoint p1,TPoint p2,TPoint p0)
{
return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
int intersect(TLineSeg u,TLineSeg v)
{
return( (max(u.a.x,u.b.x)> =min(v.a.x,v.b.x))&&
(max(v.a.x,v.b.x)> =min(u.a.x,u.b.x))&&
(max(u.a.y,u.b.y)> =min(v.a.y,v.b.y))&&
(max(v.a.y,v.b.y)> =min(u.a.y,u.b.y))&&
(multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)> =0)&&
(multiply(u.a,v.b,v.a)*multiply(v.b,u.b,v.a)> =0));
}
int online(TLineSeg l,TPoint p)
{
return( (multiply(l.b,p,l.a)==0)&&( ((p.x-l.a.x)*(p.x-l.b.x) <0 )||( (p.y-l.a.y)*(p.y-l.b.y) <0 )) );
}
int Euqal_Point(TPoint p1,TPoint p2)
{
return((abs(p1.x-p2.x) <EP)&&(abs(p1.y-p2.y) <EP));
}
int intersect_A(TLineSeg u,TLineSeg v)
{
return((intersect(u,v))&&
(!Euqal_Point(u.a,v.a))&&
(!Euqal_Point(u.a,v.b))&&
(!Euqal_Point(u.b,v.a))&&
(!Euqal_Point(u.b,v.b))/*&&
(!online(u,v.a))&&
(!online(u,v.b))&&
(!online(v,u.a))&&
(!online(v,u.b))*/);
}
int InsidePolygon(int vcount,TPoint Polygon[],TPoint q)
{
int c=0,i,n;
TLineSeg l1,l2;
l1.a=q;
l1.b=q;
l1.b.x=infinity;
n=vcount;
for (i=0;i <vcount;i++)
{
l2.a=Polygon[i];
l2.b=Polygon[(i+1)%n];
if ( (intersect_A(l1,l2))||
(
(online(l1,Polygon[(i+1)%n]))&&
(
(!online(l1,Polygon[(i+2)%n]))&&
(multiply(Polygon[i],Polygon[(i+1)%n],l1.a)*multiply(Polygon[(i+1)%n],Polygon[(i+2)%n],l1.a)> 0)
||
(online(l1,Polygon[(i+2)%n]))&&
(multiply(Polygon[i],Polygon[(i+2)%n],l1.a)*multiply(Polygon[(i+2)%n],Polygon[(i+3)%n],l1.a)> 0)
)
)
) c++;
}
return(c%2!=0);
}
float area_of_polygon(int vcount,TPoint tp[])
{
int i;
float s;
if (vcount <3) return 0;
s=tp[0].y*(tp[vcount-1].x-tp[1].x);
for (i=1;i <vcount;i++)
s+=tp[i].y*(tp[(i-1)].x-tp[(i+1)%vcount].x);
return fabs(s)/2;
}
int n;
TPoint p[1000];
void input()
{
int i;
for(i=0;i <n;i++)
cin> > p[i].x> > p[i].y;
}
int iscommondir(TPoint p1,TPoint p2,TPoint p0)
{
if(multiply(p1,p2,p0))
return 0;
else
{
double dx1=p1.x-p0.x;
double dy1=p1.y-p0.y;
double dx2=p2.x-p0.x;
double dy2=p2.y-p0.y;
double r;
if(fabs(dx1) <EP && fabs(dy1) <EP)
return 0; //??????
if(fabs(dx1) <EP)
r=dy2/dy1;
r=dx2/dx1;
if(r> 0)
return 1;
else
return 0;
}
}
int ispolygon()
{
if(n <3)
return 0;
int i,j;
TLineSeg l1,l2;
for(i=1;i <n;i++)
{
//cout < < "i: " < <i < <endl;
l1.a=p[i];
l1.b=p[(i+1)%n];
for(j=0;j <i;j++)
{
//cout < < "j: " < <j < <endl;
l2.a=p[j];
l2.b=p[(j+1)%n];
if(j==i-1)
{
if(iscommondir(p[j],p[(i+1)%n],p[i]))
{
//cout < <i < < " " < <j < < " : commondir " < <endl;
return 0;
}
}
else if(j==(i+1)%n)
{
if(iscommondir(p[i],p[(j+1)%n],p[j]))
return 0;
}
else
{
if(intersect(l1,l2))
return 0;
}
}
}
return 1;
}
int main()
{
int cas=0;
while(cin> > n,n)
{
input();
if(cas)
cout < <endl;
cas++;
cout < < "Figure " < <cas < < ": ";
double s;
if(ispolygon())
{
s=area_of_polygon(n,p);
cout.setf(ios::fixed);
cout.precision(2);
cout < <s < <endl;
}
else
cout < < "Impossible " < <endl;
}
return 0;
}
