[C++知识库]蓝桥杯大赛（大学B组）——2020省赛 平面切分 （C语言）

题目描述

平面上有 N 条直线，其中第 i 条直线是 y = Ai x + Bi 。

请计算这些直线将平面分成了几个部分。

输入描述

第一行包含一个整数 N。

以下 N 行，每行包含两个整数 Ai, Bi?。

其中，1≤N≤1000,?10^5 ≤ Ai?,Bi ?≤ 1^05。

输出描述

一个整数代表答案。

输入输出样例

示例

输入：

3
1 1
2 2
3 3

输出

6

?

题目分析

设x条直线将平面分成sum个部分

继续加入第i条直线sum增加个数=第i条直线与前i-1条直线交点个数+1

x=1时，sum=2，继续加入第2条，第3条……第N条，算出sum即可

题目代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int a[1001],b[1001];
double x[1001],y[1001];
int jd(int n)  //求第i条直线与前i+1条直线的交点个数
{
  int num=1,i,j; 
  if(n==1) return 2; //如果是第一条直线，直接返回2
  else
  {
    for(i=1;i<n;i++) //依次判断与前n-1条直线的交点个数
    {
      //printf("%d与%d条直线:",n,i);
      if(a[i]!=a[n]) //不平行时有交点
      {
        x[i]=(b[n]-b[i])*0.1/(a[i]-a[n]);
        y[i]=a[n]*x[i]+b[n];
        //printf("%.5lf %.5lf\n",x[i],y[i]); 
        int flag=0;
        for(j=1;j<i;j++) //依次判断与前i-1个交点是否相同
        {
          if(((x[i]-x[j])<0.00001&&(x[i]-x[j])>-0.00001)&&((y[i]-y[j])<0.00001&&(y[i]-y[j])>-0.00001)) flag++;
        }
        if(flag==0) num++; //如果不相同，交点num+1
      }
      //else printf("\n");
    }
    //printf("%d\n",num);
    return num;
  }
}
int main()
{
  // 请在此输入您的代码
  int n,sum=0;
  scanf("%d",&n);
  int i,j;
  for(i=1;i<=n;i++) //依次输入N条直线
  {
    scanf("%d %d",&a[i],&b[i]);
    int flag=0;
    for(j=1;j<i;j++) //排除相同的直线
    {
      if(a[j]==a[i]&&b[j]==b[i])
        flag=1;
	}
	if(flag==0) sum+=jd(i); 
  }
  printf("%d",sum);
  return 0;
}