题目连接

题目大意:

给出N(1N100)N(1\le N \le 100)条线段判断有多少个交点,(假如多个线段交于一点应重复计数)。

题目做法:

数据范围很小N2N^2枚举即可。
关于判断是否相交,先判断两条直线是否有交点,然后用叉积判断线段的两个的端点是否跨立另一条线段。

代码实践:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
const double eps=1e-10;
const double pi=acos(-1.0);
I int dcmp(double x)
{   if(fabs(x)<eps)return 0;
    else return x<0?-1:1;}
#define P point
#define PP const P &
struct point{
    double x,y;
    I P(const double &_x=0,const double &_y=0):x(_x),y(_y){}
    I bool operator ==(PP a)const{return dcmp(x-a.x)==0&&dcmp(y-a.y)==0;}
    I bool operator<(PP a)const{return x<a.x||(x==a.x&&y<a.y);}
    I P operator+(PP a)const{return P(x+a.x,y+a.y);}
    I P operator-(PP a)const{return P(x-a.x,y-a.y);}
    I P operator*(const double a)const{return P(x*a,y*a);}
    I P operator/(const double a)const{return P(x/a,y/a);}
    I P operator*(PP a)const{return P(x*a.x-y*a.y,x*a.y+y*a.x);}
    I double len()const{return sqrt(x*x+y*y);}
    I double len2()const{return x*x+y*y;}
    I P rotate(const double theta)const{return P(x,y)*P(cos(theta),sin(theta));}
    I double operator|(PP a)const{return x*a.x+y*a.y;}
    I double operator&(PP a)const{return x*a.y-y*a.x;}
    I P norm(){return *this/len();}
    I double angle(PP a)const{return *this|a/len()/a.len();}
};
typedef point vec;
const int maxn=110;
struct line{
    P a,b;
}L[maxn];
I int D_pos(PP q,const line A){
    vec k1=q-A.a,k2=A.b-A.a;
    return dcmp(k1&k2); 
}
I bool across(const line &a,const line &b){
    int ans1=D_pos(a.a,b);
    int ans2=D_pos(a.b,b);
    int ans3=D_pos(b.a,a);
    int ans4=D_pos(b.b,a);
    if((ans1&ans2&ans3&ans4)==0)return 1;
    if(ans1!=ans2&&ans3!=ans4)
    return 1;
    else return 0;
}
I bool check(const line &a,const line & b){
    vec k1=a.b-a.a,k2=b.b-b.a;
    if(dcmp(k1&k2)==0)return 0;
    else return across(a,b);
}
signed main(){
    int n;
    while(scanf("%d",&n)&&n!=0){
        memset(L,0,sizeof L);
        FOR(i,1,n)
            scanf("%lf%lf%lf%lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y);
        int ans=0;
        FOR(i,1,n)
            FOR(j,i+1,n)
                ans+=check(L[i],L[j]);
        printf("%d\n",ans);
    }
    return 0;
}