#include<iostream>
using namespace std;

typedef struct node
{
 double x;
 double y;
}Node;

Node star[100],end[100];
int max_dian,N;          //N条直线；

double max(double a,double b)
{
 return a>b?a:b;
}
double min(double a,double b)
{
 return a<b?a:b;
}

double Direction(Node p1,Node p2,Node p)  //判断p与线段p1p2 的位置关系,p1当作"原点";
{
 return (p2.x-p1.x)*(p.y-p1.y)-(p.x-p1.x)*(p2.y-p1.y); 
}

bool online(Node p1,Node p2,Node p)  //判断p是否在p1p2上；
{
 double max=p1.y>p2.y?p1.y:p2.y;
 double min=p1.y>p2.y?p2.y:p1.y;

    if(  p.y>=min  &&  p.y<=max )   return true;
    return false;
}

bool cross(Node p1,Node p2,Node p3,Node p4)
{
 double d1=Direction(p1,p2,p3);
 double d2=Direction(p1,p2,p4);
 double d3=Direction(p3,p4,p1);
 double d4=Direction(p3,p4,p2);
 if(  d1*d2<0   &&   d3*d4<0   )      return true; 
 if(  d1==0 && online(p1,p2,p3))      return true;//d1=0说明p3在p1_p2上，                                                     ；
    if(  d2==0 && online(p1,p2,p4))      return true;//还要判断是否在线段上
    if(  d3==0 && online(p3,p4,p1))      return true;
    if(  d4==0 && online(p3,p4,p2))      return true;
 return false;
}

void find_set()
{
 max_dian=0;
 for(int i=1;i<=N;i++)
 {
  for(int j=i+1;j<=N;j++)
  {
   if(cross(star[i],end[i],star[j],end[j]))
    max_dian++;
  }
 }
 printf("%d\n",max_dian);
}

int main()
{
 freopen("D:\\in.txt","r",stdin);
 while( scanf("%d",&N),N)
 {
  for(int i=1;i<=N;i++)
  {
   scanf("%lf%lf%lf%lf",&star[i].x,&star[i].y,&end[i].x, &end[i].y);
  }
  find_set();
 }
 return 0;
}

数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找去其中一个连续子序列 ， 使
和最大。
这个问题可以可以动态规划的思想解决：
设 b[i]: 表示以第 i 个元素 a[i] 结尾的最大子序列 , 那么显然
b[i+1]=b[i]>0?b[i]+a[i+1]
基于这一点很快就可以完成如下代码 :
int maxSubArray( int ar[], int n)
{
int max = ar[0];
int b = ar[0];
int i;
for (i = 1; i < n; i++)
{
if (b > 0)
b += ar[i];
else
b = ar[i];
if (b > max)
max = b;
}
return max;
}
扩展问题 : 给定一个矩阵 ( 二维数组 ), 其中数据有大有小 , 请找一个子矩阵 , 使得子矩阵的和最大 , 并
输出这个和
同样可以利用动态规划的思想来解决我们想 , 如果确定了选择第 i 列和第 j 列之间的元素 ， 那么在这个范围内 ， 其实就是一个最大子序
列问题
现在确定第 i 列和第 j 列间，我用的是暴搜
代码如下：
int maxSubMatrix( int (*ma)[4], int m, int n)
{
int i, j, k, max = ma[0][0], tmp;
// 记录每行的和
int * sum = malloc(m * sizeof( int ));
for (i = 0; i < n; i++)
{
for (k = 0; k < m; k++)
sum[k] = 0;
for (j = i; j < n; j++)
{
for (k = 0; k < m; k++)
{
sum[k] += ma[k][j];
}
tmp = maxSubArray(sum, n);
if (tmp > max)
max = tmp;
}
}free(sum);
return max;
}
测试代码
int main()
{
int a[] = {-3, 4, 7, -9, 10, 21, -3, 5, 9};
int ma[3][4] = {-1, 3, 4, 5, 2, 1, 6, 7, 8, -9, -10, 20};
printf(" %d\n ", maxSubArray(a, 9));
printf(" %d\n ", maxSubMatrix(ma, 3, 4));
return 0;
}

算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

#include<stdio.h>
#include<string.h>
 
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
 
bool init()
{
        int _x,_y;
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        ans=0;
        if(scanf("%d%d",&n,&m)==EOF)return false;
        for(int i=1;i<=n;i++)
        {
                scanf("%d",&_x);
                for(int j=0;j<_x;j++)
                {
                        scanf("%d",&_y);
                        g[ i ][_y]=true;
                }
        }
        return true;
}
 
bool find(int a)
{
        for(int i=1;i<=m;i++)
        {
                if(g[a][ i ]==1&&!b[ i ])
                {
                        b[ i ]=true;
                        if(link[ i ]==0||find(link[ i ]))
                        {
                                link[ i ]=a;
                                return true;
                        }
                }
        }
        return false;
}
 
int main()
{
        while(init())
        {
                for(int i=1;i<=n;i++)
                {
                        memset(b,0,sizeof(b));
                        if(find(i))ans++;
                }
                printf("%d\n",ans);
        }
}

每次增广时间为O(E),最多进行O(V)次迭代,时间复杂度为O(VE).