精华内容
下载资源
问答
  • 平面切分

    2021-04-13 14:39:39
    平面切分 问题描述 题解: 我对这种题极其非常不擅长。。。 另外吐槽为什么acwing的数据卡的这么死,蓝桥杯官网数据那么水 其实题目很简单,如果只有一个直线,那么就是两部分,如果是两个直线,这两个直线不相交...

    平面切分

    问题描述

    在这里插入图片描述

    题解:

    我对这种题极其非常不擅长。。。
    另外吐槽为什么acwing的数据卡的这么死,蓝桥杯官网数据那么水
    其实题目很简单,如果只有一个直线,那么就是两部分,如果是两个直线,这两个直线不相交(也就是平行),就是三部分,不想交就是四部分。。。然后枚举跟多的例子你会发现,平面的数量与直线的交点有关系,我们设一开始平面数为2(也就是一开始有一个直线),增加的平面数量为交点数+1,然后你每次加入新的直线,求之前直线的交点,然后用set存就可以了。但是注意注意!!有可能会出现重合或者平行的直线,对于平行的我们不管他,对于重合的,我们直接跳出当前循环,因为既然重合,说明之前那个直线都和其他的直线算过了,所以当前直线就不能再算了(否则会重复)

    代码:

    acwing最后一个点过不去

    #include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
       return s*w;
    }
    const int maxn=1005;
    double a[maxn],b[maxn];
    set<pair<double ,double > >s;
    set<pair<double ,double > >::iterator it;
    bool f[maxn];
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		double x,y;
    		cin>>x>>y;
    		s.insert(make_pair(x,y));
    	}
    	int tot=0;
    	for(it=s.begin();it!=s.end();it++)
    	{
    		a[tot]=(*it).first;
    		b[tot]=(*it).second;
    		tot++; 
    	}
    	ll ans=2;
    	for(int i=1;i<s.size();i++)
    	{
    		set<pair<double ,double > >se;
    		for(int j=i-1;j>=0;j--)
    		{
    			if(abs(a[i]-a[j])<0.0001)
    			{
    				if(abs(b[i]-b[j])<0.0001)
    				{
    					f[i]=1;
    					break;
    				}
    				else continue;
    			}			
    			double x=(-1.0)*(b[i]-b[j])/(a[i]-a[j]);
    			double y=x*a[i]+b[i];
    			se.insert(make_pair(x,y));
    		}
    		if(f[i]!=1)
    			ans+=(se.size()+1);
    	}
    	cout<<ans;
    }
    
    
    展开全文
  • 蓝桥杯 平面切分

    2021-04-17 10:23:12
    试题 历届试题 平面切分 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 平面上有 条直线,其中第 条直线是 。 请计算这些直线将平面分成了几个部分。 输入格式 第一行包含一个整数 。 以下N行,每行包含两个...

    试题 历届试题 平面切分

    资源限制
    时间限制:1.0s 内存限制:256.0MB
    问题描述
    平面上有 条直线,其中第 条直线是 。

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

    输入格式
    第一行包含一个整数 。

    以下N行,每行包含两个整数 。

    输出格式
    一个整数代表答案。

    样例输入
    3
    1 1
    2 2
    3 3
    Data
    样例输出
    6

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <set>
    #include <algorithm>
    using namespace std;
    
    long double s[1005][2];
    long long ans ;
    bool st[1005];
    pair<long double,long double> p;
    
    int main() {
        int n; scanf("%d",&n);
        for(int i=0; i<n; i++) {
            cin >> s[i][0] >> s[i][1];
            set<pair<long double,long double> > points;
            for(int j=0; j<i; j++) {
    //            if(st[j]) continue;// 是重边
    //            if(s[i][0] == s[j][0]) {// 斜率相等  平行或者 重合
    //                if(s[i][1] == s[j][1]) {
    //                    //st[i] = true;
    //                    break;
    //                }
    //                else continue;// 平行的时候不需要计算交点
    //            }
                p.first = (s[j][1] - s[i][1]) / (s[i][0] - s[j][0]);//交点x坐标
                p.second = p.first * s[i][0] + s[i][1];
                points.insert(p);
            }
            if(!st[i]) ans += points.size() + 1;
        }
        cout << ans + 1 << endl;
        return 0;
    }
    
    展开全文
  • I平面切分

    2021-04-16 23:32:09
    平面切分1. 原题题目2. 解题思路3. Ac代码 2021.4.16 1. 原题题目 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 平面上有 条直线,其中第 条直线是 。 请计算这些直线将平面分成了几个部分。 输入格式 第一...

    蓝桥杯第十一届 I.平面切分


    2021.4.16

    1. 原题题目

    资源限制
    时间限制:1.0s 内存限制:256.0MB
    问题描述
    平面上有 条直线,其中第 条直线是 。

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

    输入格式
    第一行包含一个整数 。

    以下N行,每行包含两个整数 。

    输出格式
    一个整数代表答案。

    样例输入
    3
    1 1
    2 2
    3 3
    样例输出
    6
    评测用例规模与约定
    对于50的评测用例:
    1 <= N <= 4,-10 <= Ai,Bi <= 10
    对于所有评测用例:
    1 <= N <= 1000,-100000 <= Ai,Bi <= 100000

    2. 解题思路

    分两步走:
    第一步:找规律,根据平面中线的个数计算切分的平面数量
    两种情况:
    (1)新增加的线与原来的线没有交点,则平面数量+1
    (2)如果新增的线与原先的线有交点,则新增的平面数量 = 交点个数 + 1
    这里的1是原先平面就有一个
    第二步:注意点:
    (1)重边需要删除,用set即可实现,例如样例中有个测试点n=4,A,B都是0,注意后面对交点进行计算的时候,遍历的范围不是n,而是set.size()
    (2)遇到平行边时,跳过不计算
    (3)平面数量ans初始化为0,1,2都行,与后面从第几条线开始遍历有关
    (4)求交点公式
    x =1.0 * (x2-x1) / (y1 - y2)
    将x带入原来的公式计算出y。注意这里计算都要乘上一个1.0(我也不知道为啥,不乘的话有5个样例点过不去)

    3. Ac代码

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define ld long double
    const int maxn = 1e3 + 10;
    ll a[maxn][2];//存放去重后的A,B
    pair<ld,ld> p;
    int main(){
        ios::sync_with_stdio(false),cin.tie(0);
        int n,A,B;
        ll ans = 1;//初始化为,没有直线时就是一个平面
        cin >> n;
        set<pair<ld,ld> >s;//作用:去掉重边
        for (int i = 0; i < n; i++){
            cin >> A >> B;
            p.first = A;
            p.second = B;
            s.insert(p);
        }
        //将去重后的边加入到二维数组
        int i = 0;
        for (set<pair<ld,ld> > :: iterator it= s.begin(); it != s.end(); i++,it++){
            a[i][0] = it->first;
            a[i][1] = it->second;
        }
        /*检查数组元素
        for (int i = 0; i < s.size(); i++){
            for (int j = 0; j < 2; j++)
                cout << a[i][j] << " ";   
            cout << '\n';     
        }*/
        for (int i = 0; i < s.size(); i++){
            set<pair<ld,ld> > sp;
            for (int j = 0; j < i; j++){
                if (a[i][0] == a[j][0]) continue;
                p.first = 1.0 * (a[j][1] - a[i][1]) / (a[i][0] - a[j][0]);//计算交点x
                p.second = 1.0 * p.first * a[i][0] + a[i][1];//计算交点y
                sp.insert(p);
            }
            ans += sp.size() + 1;
        }
        cout << ans << '\n';
        return 0;
    }
    
    展开全文
  • 蓝桥杯——平面切分

    2021-04-15 21:26:19
    平面切分 平面切分 输入描述 第一行包含一个整数N。 以下NN行,每行包含两个整数Ai​,Bi​。 其中,1≤N≤1000,−10^5≤Ai​,Bi​≤10^5。 输出描述 一个整数代表答案。 输入输出样例 示例 输入 3 1 1 ...

    题目描述

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

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

    题目链接:

    第一个有时提交会显示系统错误,建议使用第二个链接。

    平面切分

    平面切分

    输入描述

    第一行包含一个整数 N。

    以下 NN 行,每行包含两个整数Ai​,Bi​。

    其中,1≤N≤1000,−10^5≤Ai​,Bi​≤10^5。

    输出描述

    一个整数代表答案。

    输入输出样例

    示例

    输入

    3
    1 1
    2 2
    3 3

    输出

    6

     

     分析这道题,首先假如输入的n条直线为平行直线既输入所有的直线的Ai都相等且不重合的情况下平面被分为n+1个平面,我们假设每条直线自身的权值为1。假如当平面上只有一条直线时平面被分为两个平面,此时如果多一条直线变为两条直线后我们分情况讨论。

    第一:如果这两条直线平行(不考虑重和的情况)则分后的平面为1+1+1=3,即两条直线的权值相加并+1。

    第二:如果这两条直线相交,此时我们可以发现平面被分为四个平面,此时我们记每条直线的权值为这条直线原有的权值1加上这条直线经过交点的个数。我们记第一条直线的权值总为1。所以平面个数即第一条直线权值1加第二条直线权值2再加1。

    第3……n条直线以此类推。

    首先定义结构体用于储存直线的xi,yi与斜率zi

    typedef struct mu
    {
    	lb x; //储存变量x的系数a
    	lb y; //储存常量b
    	lb z; //储存斜率
    }M;

    为方便记录交点为坐标我们用pair定义:

    pair<lb, lb> P;

    求解结果:

    int ans = 0;
    	for (int i = 1; i <= n; i++)
    	{
    		int flag = 0;
    		cin >> x >> y;
    		m[i].z = x;
    		m[i].x = x;
    		m[i].y = y;
    		set<pair<lb, lb> > poin;    //利用set容器的特性可以使每个元素的个数只为1
    		for (int j = 1; j < i; j++)
    		{ 
    			if (m[i].z == m[j].z)    //如果有两条直线斜率相等
    			{
    				if (m[i].y == m[j].y) //判断是否为同一条直线,即是否重合
    				{
    					flag = 1;
    					break;            //如果直线重合则不进行以下操作,因为在之前已经进行过
    				}
    				else
    					continue;
    			}
                //求直线m[i]与直线m[j]的交点坐标
    			P.first = (m[i].y - m[j].y) / (m[j].x - m[i].x); 
    			P.second = (m[i].x)*P.first + m[i].y;
                //储存在poin中。
    			poin.insert(P);
    		}
    		
            //如果flag == 1则证明这条直线在之前已经存在过,不进行计算
    		if (flag != 1)
    			ans += poin.size() + 1;  //求所有直线的权值之和
    	}
        cout<<ans+1; //结果为所有直线的权值和加1;

    完整代码:

    #include<iostream>
    #include<bits/stdc++.h>
    typedef long double lb;
    using namespace std;
    
    typedef struct mu
    {
    	lb x;
    	lb y;
    	lb z;
    }M;
    
    pair<lb, lb> P;
    
    int main()
    {
    	int n;
    	M m[1010];
    	cin >> n;
    
    	lb x, y;
    	int ans = 0;
    	for (int i = 1; i <= n; i++)
    	{
    		int flag = 0;
    		cin >> x >> y;
    		m[i].z = x;
    		m[i].x = x;
    		m[i].y = y;
    		set<pair<lb, lb> > poin;
    		for (int j = 1; j < i; j++)
    		{
    			if (m[i].z == m[j].z)
    			{
    				if (m[i].y == m[j].y)
    				{
    					flag = 1;
    					break;
    				}
    				else
    					continue;
    			}
    			P.first = (m[i].y - m[j].y) / (m[j].x - m[i].x);
    			P.second = (m[i].x)*P.first + m[i].y;
    			poin.insert(P);
    		}
    		
    		if (flag != 1)
    			ans += poin.size() + 1;
    	}
    
    	cout << ans + 1;
    	return 0;
    }

     

     

     

    展开全文
  • 蓝桥杯:平面切分

    2021-04-16 08:14:52
    平面切分: 我们把直线新产生的交点设为n可以知道当一个平面只有一条直线时,平面被分成两半共分成2块; 共两块 当平面有两条直线时,有两种情况:‌ 与第一条直线平行,也就是没有交点,此时平面被分成三块,n=0,...
  • 十一届蓝桥杯B组试题:平面切分

    千次阅读 2021-01-22 13:36:18
    十一届蓝桥杯B组试题:平面切分 试题 I: 平面切分 时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分 【问题描述】 平面上有 N 条直线,其中第 i 条直线是 y = Ai · x + Bi。 请计算这些直线将平面分成了几个部分...
  • 平面切分欧拉定理的应用
  • 2020第十一届蓝桥杯C/C++ B组 平面切分
  • 试题 历届试题 平面切分 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 平面上有 条直线,其中第 条直线是 。 请计算这些直线将平面分成了几个部分。 输入格式 第一行包含一个整数 。 以下N行,每行包含两个...
  • 第十一届蓝桥杯省赛第二场真题(python组)——平面切分(注释详细) 试题 I: 平面切分 时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分 【问题描述】 平面上有 N 条直线,其中第 i 条直线是 y = Ai · x + Bi。...
  • I:平面切分

    2021-04-17 10:10:21
    分析: 1. 斜率相等时: 1)重边不会增加区域数 2)不是重边会增加一个区域 2. 斜率不同时: 与其他边每有一个交点就会增加一个区域数 代码如下: #include<iostream> #include<...ty...
  • 平面切分--蓝桥杯

    2021-02-24 20:31:28
    平面上有 N 条直线,其中第 i 条直线是 y = Ai · x + Bi。 请计算这些直线将平面分成了几个部分。 【输入格式】 第一行包含一个整数 N。 以下 N 行,每行包含两个整数 Ai, Bi。 【输出格式】 一个整数代表答案。 ...
  • //没有直线时有一个平面 float jd[max_size][2];//交点可能含小数,故用float型 void f(int i,int arr[1010][2],int a,int b) { int temp=0;//统计当前直线与在它之前直线的不同交点数 for(int j=1;j<i;j++) ...
  • 蓝桥杯 平面切分(欧拉定理)

    千次阅读 2021-03-18 15:41:02
    平面上有 N条直线,其中第 i条直线是 y = Ai*x + B。 请计算这些直线将平面分成了几个部分。 输入格式 第一行包含一个整数N。 以下N行,每行包含两个整数 Ai, Bi。 输出格式 一个整数代表答案。 样例输入 3 1 1 2 2 ...
  • 平面上有 N 条直线,其中第 i 条直线是y=Ai*x+Bi。 请计算这些直线将平面分成了几个部分。 输入描述 第一行包含一个整数 N。 以下 N 行,每行包含两个整数 Ai, Bi。 其中,1≤N≤1000,−10^ 5 ≤ Ai,Bi ≤ 10 ^5。 ...
  • 平面切分空间

    千次阅读 2011-02-12 21:35:00
      n条直线最多把平面分成C(n,0)+C(n,1)+C(n,2)份;  n个平面最多把空间分成C(n,0)+C(n,1)+C(n,2)+C(n,3)=(n³+5n+6)/6份;  n个空间最多把“时空”分成C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)份;...
  • 平面上有 条直线,其中第 条直线是 。 请计算这些直线将平面分成了几个部分。 输入格式 第一行包含一个整数 。 以下N行,每行包含两个整数 。 输出格式 一个整数代表答案。 样例输入 3 1 1 2 2 3 3 Data 样例输出 6 ...
  • 第十一届蓝桥杯C/C++ 试题I 平面切分

    千次阅读 多人点赞 2020-10-27 19:57:10
    水了个省一,写个题解        ...因为之前没做过几何题,粗看一眼,感觉...当添加一条直线时,这条直线与当前平面内已有直线每产生一个不同位置的交点时,这条直线对平面数量的贡献

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 146
精华内容 58
关键字:

平面切分