重庆网站开发服务器,中国肩章,河北工程信息网,广东网站建设费用问题 Description
线段求交即给定一组线段求出这些线段的相交情况#xff0c;它是计算几何的基础问题之一,有着广泛的应用.
Input第一行为一个正整数n表示线段的个数#xff08;n10000#xff09;第二行到第n1行每行包括4个正整数x1,y1,x2,y2, (0 x1,y1,x2,y2 … 问题 Description
线段求交即给定一组线段求出这些线段的相交情况它是计算几何的基础问题之一,有着广泛的应用.
Input第一行为一个正整数n表示线段的个数n10000第二行到第n1行每行包括4个正整数x1,y1,x2,y2, (0 x1,y1,x2,y2 1000) x1x2表示线段两端点的横坐标y1y2表示线段两端点的纵坐标注意线段的两端点可能重合 即(x1,y1)有可能等于(x2,y2)
Output一个正整数k, 表示相交的线段对数这里只要两线段有接触即为相交.数据保证k100000.
Sample Input
8
10 13 20 56
37 60 40 7
87 57 113 5
96 16 125 51
171 4 231 4
200 4 211 43
268 36 354 36
283 4 314 36
Sample Output
3 TLE代码 #includestdio.h
#define N 10002/**
算法适用于整形点不适用于浮点型
**/typedef struct Point
{int x;int y;
}Point;double min(int x, int y)
{return xy?x:y;
}double max(int x, int y)
{return xy?x:y;
}//排斥实验
bool IsRectCross(const Point p1,const Point p2,const Point q1,const Point q2)
{bool ret min(p1.x,p2.x) max(q1.x,q2.x) min(q1.x,q2.x) max(p1.x,p2.x) min(p1.y,p2.y) max(q1.y,q2.y) min(q1.y,q2.y) max(p1.y,p2.y);return ret;
}
//跨立判断
bool IsLineSegmentCross(const Point P1,const Point P2,const Point Q1,const Point Q2)
{if(((Q1.x-P1.x)*(Q1.y-Q2.y)-(Q1.y-P1.y)*( Q1.x-Q2.x)) * ((Q1.x-P2.x)*(Q1.y-Q2.y)-(Q1.y-P2.y)*(Q1.x-Q2.x)) 0 ||((P1.x-Q1.x)*(P1.y-P2.y)-(P1.y-Q1.y)*(P1.x-P2.x)) * ((P1.x-Q2.x)*(P1.y-P2.y)-(P1.y-Q2.y)*( P1.x-P2.x)) 0) return true;elsereturn false;
}int main() //O(n^2)
{int n,i,j;Point arr[N][2];int count; while(scanf(%d,n)!EOF n!0)//第一行为一个正整数n表示线段的个数n10000{count0;for(i1;in;i)scanf(%d %d %d %d, arr[i][0].x, arr[i][0].y, arr[i][1].x,arr[i][1].y); //第二行到第n1行每行包括4个正整数x1,y1,x2,y2, (0 x1,y1,x2,y2 1000) for(i1; in; i)for(ji1; jn; j)if(IsRectCross(arr[i][0],arr[i][1],arr[j][0],arr[j][1])IsLineSegmentCross(arr[i][0],arr[i][1],arr[j][0],arr[j][1]))count;printf(%d\n,count);}return 0;
}/**
8
10 13 20 56
37 60 40 7
87 57 113 5
96 16 125 51
171 4 231 4
200 4 211 43
268 36 354 36
283 4 314 36
**//**************************************************************Problem: 1171User: cld378632668Language: CResult: Time Limit Exceed
****************************************************************/ AC 代码 #include stdio.h
#include string.h
#define p(x1,y1,x2,y2,a,b) ((y2-y1)*(a-x1)(y1-b)*(x2-x1))
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
int main()
{#ifndef ONLINE_JUDGEfreopen(1.in,r,stdin);
// freopen(1.out,w,stdout);#endif // ONLINE_JUDGEint n,m;scanf(%d,n);int x1[n1],y1[n1],x2[n1],y2[n1],i,j,a,b,c,d,sum0;for (i1;in;i)scanf(%d%d%d%d,x1i,y1i,x2i,y2i);for (i1;in;i)for (ji1;jn;j){ap(x1[j],y1[j],x2[j],y2[j],x1[i],y1[i]);bp(x1[j],y1[j],x2[j],y2[j],x2[i],y2[i]);cp(x1[i],y1[i],x2[i],y2[i],x1[j],y1[j]);dp(x1[i],y1[i],x2[i],y2[i],x2[j],y2[j]);if (!a !b !c !d){if (max(x1[i],x2[i])min(x1[j],x2[j]) max(x1[j],x2[j])min(x1[i],x2[i]) max(y1[i],y2[i])min(y1[j],y2[j]) max(y1[j],y2[j])min(y1[i],y2[i]))sum;}else{if ((a0 b0 || a0 b0) (c0 d0 || c0 d0)){sum;//printf(%d %d\n,i,j);}}}printf(%d\n,sum);return 0;
}
