Question

ACM问题 我的代码哪里错了？？ http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1382

http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1382
我的代码：
#include <iostream>
using namespace std;
#define eps 1.0e-5
inline double max(double a,double b) { return a>b?a:b; }
inline double min(double a,double b) { return a<b?a:b; }
inline double dabs(double a) { return a<0?-a:a; }
struct point
{
double x,y;
};
point a[4],b[4];
bool online(const point& p1,const point& p2,const point& p3)
{
if(p2.x>=min(p1.x,p3.x)&&p2.x<=max(p1.x,p3.x)
&&p2.y>=min(p1.y,p3.y)&&p2.y<=max(p1.y,p3.y))
{
if(dabs((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))<=eps)
return true;
}
return false;
}
int in(point *a,int n,point p)
{
int counter=0;
double xinters;
point p1,p2;
p1=a[0];
for(int i=1;i<=n;i++)
{
p2=a[i%n];
if(online(p1,p,p2))
return 2;
if(p.y>min(p1.y,p2.y))
{
if(p.y<=max(p1.y,p2.y))
{
if(p.x<=max(p1.x,p2.x))
{
if(p1.y!=p2.y)
{
xinters=(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if(p1.x==p2.x||p.x<=xinters)
counter++;
}
}
}
}
p1=p2;
}
if(counter%2==0)
return 0;
return 1;
}
int main()
{
while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a[0].x,&a[0].y,&a[1].x,&a[1].y,&a[2].x,&a[2].y,&a[3].x,&a[3].y)!=EOF)
{
int i,j;
int aa[4],bb[4];
for(i=0;i<=3;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
for(i=0;i<4;i++)
aa[i]=in(b,4,a[i]);
for(i=0;i<4;i++)
bb[i]=in(a,4,b[i]);
if(aa[0]!=0&&aa[1]!=0&&aa[2]!=0&&aa[3]!=0)
{
printf("IN\n");
continue;
}
else if(aa[0]==0&&aa[1]==0&&aa[2]==0&&aa[3]==0&&bb[0]==0&&bb[1]==0&&bb[2]==0&&bb[3]==0)
{
printf("OUT\n");
continue;
}
else
printf("OVERLAPPED\n");
}
}

Answer 1

//1382 Accepted 0MS 182K

//1.求凸包，这是为了算包含关系，如果凸包点数为4，
//判断4个点是否刚好属于其中一个矩形的，如果是A，说明A包含B，
//如果是B，则B包含A，否则进入重叠判断
//2.判断重叠，穷举每条线段判断是否相交即可

#include<iostream>
#include <algorithm>
#include <CMATH>
using namespace std;
const double eps=1e-10; //允许的误差
struct point //点的结构体
{
double x, y;
friend bool operator!=(const point &l, const point &r)
{
if (l.x!=r.x && l.y!=r.y)
{
return true;
}
return false;
}
friend bool operator < (const point &l, const point &r){
return l.y < r.y || (l.y == r.y && l.x < r.x);
}
};

double min(double a, double b) { return a < b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
bool inter(point a, point b, point c, point d) //判断线段相交
{
if ( min(a.x, b.x) > max(c.x, d.x) ||
min(a.y, b.y) > max(c.y, d.y) ||
min(c.x, d.x) > max(a.x, b.x) ||
min(c.y, d.y) > max(a.y, b.y) ) return 0;
double h, i, j, k;
h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
return h * i <= eps && j * k <= eps;
}

bool mult(point sp, point ep, point op)
{
return (sp.x - op.x) * (ep.y - op.y)
>= (ep.x - op.x) * (sp.y - op.y);
}
point num[8];
point t1[8];
point t2[8];

int graham(point pnt[], int n, point res[]) //求凸包
{
int i, len, k = 0, top = 1;
sort(pnt, pnt + n);
if (n == 0) return 0; res[0] = pnt[0];
if (n == 1) return 1; res[1] = pnt[1];
if (n == 2) return 2; res[2] = pnt[2];
for (i = 2; i < n; i++) {
while (top && mult(pnt[i], res[top], res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n - 2];
for (i = n - 3; i >= 0; i--) {
while (top!=len && mult(pnt[i], res[top],
res[top-1])) top--;
res[++top] = pnt[i];
}
return top; // 返回凸包中点的个数
}
int main()
{
int i,j,k,l;
while (scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",
&num[0].x,&num[0].y,&num[1].x,&num[1].y,&num[2].x,&num[2].y,
&num[3].x,&num[3].y,&num[4].x,&num[4].y,&num[5].x,&num[5].y,
&num[6].x,&num[6].y,&num[7].x,&num[7].y)!=EOF)
{
for (i=0;i<8;i++)
t2[i]=num[i];
sort(t2+4, t2 + 8);
sort(t2, t2 + 4);
int sum=graham(num,8,t1);
if(sum==4)
{
sort(t1,t1+4);
for (i=0;i<4;i++)
{
if(t2[i+4]!=t1[i])
break;
}
if (i==4)
{
printf("IN\n");
continue;;
}
for (i=0;i<4;i++)
{
if(t2[i]!=t1[i])
break;
}
if (i==4)
{
printf("OUT\n");
continue;;
}
}
else
{
bool judge=false;
for (i=0;i<3;i++)
{
for (j=i+1;j<4;j++)
{
for (k=4;k<8;k++)
{
for (l=k+1;l<8;l++)
{
if (inter(t2[i],t2[j],t2[k],t2[l]))
{
judge=true;
break;
}
}
if (judge)
{
break;
}
}
if (judge)
{
break;
}
}
if (judge)
{
break;
}
}
if (judge)
{
printf("OVERLAPPED\n");
}
else
printf("OUT\n");
}
}
return 0;
}