欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[POJ2653]Pick-up sticks(计算几何-叉积)

程序员文章站 2022-04-01 14:47:07
...

题目:

我是超链接

题解:

两条线段的交点,那就像直线和线段的交点那样吧,假设线段A,B,所含四个点a,b,c,d
a与c的方向向量和A的方向的叉积*a与d的方向向量和A的方向的叉积应当小于0(不在同一侧)
因为是线段,我们对于d也应该判断一遍,d与a,d与b
不过这个题。。别看是多组数据+n的范围,其实O(n2)能过?!

代码:

#include <cstdio>
#include <cstring>
using namespace std;
const double eps=1e-9;
const int N=100005;
bool vis[N];int ans[N];
int dcmp(double x)
{
    if (x<=eps && x>=-eps) return 0;
    return (x>0)?1:-1;
}
struct po
{
    double x,y;
    po(double X=0,double Y=0){x=X;y=Y;}
};
struct line
{
    po x,y;
    line(po X=po(0,0),po Y=po(0,0)){x=X;y=Y;}
}l[N];
po operator -(po x,po y){return po(x.x-y.x,x.y-y.y);}
double cj(po x,po y){return x.x*y.y-x.y*y.x;}
bool check(line x,line y)//如果相交 
{
    po a=x.x,b=x.y,c=y.x,d=y.y;
    double d1=dcmp(cj(a-c,a-b)),d2=dcmp(cj(a-d,a-b));
    double d3=dcmp(cj(d-a,d-c)),d4=dcmp(cj(d-b,d-c));
    return d1*d2<=0&&d3*d4<=0;
}
int main()
{
    int n;
    while (scanf("%d",&n)&&n)
    {
        memset(vis,0,sizeof(vis));
        for (int i=1;i<=n;i++)
        {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            l[i].x=po(x1,y1); l[i].y=po(x2,y2);
        }
        for (int i=1;i<=n;i++)
          for (int j=i+1;j<=n && !vis[i];j++)
            if (check(l[i],l[j])) vis[i]=1;
        int s=0;
        for (int i=1;i<=n;i++)
          if (!vis[i]) ans[++s]=i;
        printf("Top sticks:");
        for (int i=1;i<s;i++) printf(" %d,",ans[i]);
        printf(" %d.\n",ans[s]);
    }
}
相关标签: 计算几何 叉积