[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的范围,其实
代码:
#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]);
}
}
上一篇: CanvasTurtle :使用javaScript 与 Canvas
下一篇: 三维几何-三角形
推荐阅读
-
2020 年百度之星·程序设计大赛 - 测试赛 度度熊保护村庄 计算几何(叉积)+floyd(最小环)
-
计算几何——Pick-up sticks(线段相交)
-
计算几何 POJ 2653 Pick-up sticks
-
2018.07.03 POJ 2653 Pick-up sticks(简单计算几何)
-
2020 年百度之星·程序设计大赛 - 测试赛 度度熊保护村庄 计算几何(叉积)+floyd(最小环)
-
计算几何 - 点积与叉积
-
[POJ2653]Pick-up sticks(计算几何-叉积)
-
[POJ3304]Segments(计算几何-叉积)
-
[POJ1269]Intersecting Lines(计算几何-叉积)
-
CSUOJ 1503: 点到圆弧的距离 [叉积+三角形外心]【计算几何】