蓝桥杯2020年第十一届省赛真题-平面切分

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long double x,y;
}a[100005];
int main()
{
	set< pair<long double,long double> >st;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		long double x,y;
		cin>>x>>y;
		st.insert(make_pair(x,y));
	}
	int j=0;
	for(auto i=st.begin();i!=st.end();i++)
	{
		a[j].x= (*i).first;
		a[j++].y= (*i).second;
	}
	int ans=1;
	for(int i=0;i<j;i++)
	{
		set< pair<long double,long double> >point;
		
		for(int k=i;k>=0;k--)
		{
			if(a[i].x==a[k].x)continue;
			long double x;
			x=a[k].y-a[i].y;
			x/=a[i].x-a[k].x;
			long double y;
			y=a[i].x*x+a[i].y;
			point.insert(make_pair(x,y));
		}
		//cout<<point.size();
		ans+=point.size()+1;
		point.clear();
	}
	cout<<ans;
	return 0;
}