欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Benelux Algorithm Programming Contest 2019 K. Keep Him Inside 高中数学题

程序员文章站 2022-06-04 12:25:22
...

Benelux Algorithm Programming Contest 2019 K. Keep Him Inside 高中数学题

以上,是为什么这题可以ON扫描的证明。只要P在我们枚举的三角形内部,就一定能找到a,b,c满足题意的解。

然后就是解二元一次方程就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const double eps=1e-8;
const int M = 1e5+7;
/*
int head[M],cnt;
void init(){cnt=0,memset(head,-1,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y){ee[++cnt].nxt=head[x],ee[cnt].to=y,head[x]=cnt;}
*/

struct node{
	double x,y,z;
}p[11];
int main()
{
	int n;
	double px,py;
	scanf("%d%lf%lf",&n,&px,&py);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	for(int j=2;j<n;j++)
	{
		int i=1,k=j+1;
		node a={p[i].x-p[k].x,p[j].x-p[k].x,px-p[k].x};
		node b={p[i].y-p[k].y,p[j].y-p[k].y,py-p[k].y};
		double q=a.x*b.y-a.y*b.x;//由于无三点共线,则q不可能为0 ,只要P在三角形内,一定保证a>0,b>0,1-a-b>0 
		double A,B,C;
		A=(a.z*b.y-b.z*a.y)/q;
		B=(a.x*b.z-a.z*b.x)/q;
		C=1.0-A-B;
		if(A+eps>=0&&B+eps>=0&&C+eps>=0)
		{
			for(int z=1;z<=n;z++)
			{
				if(z==i)printf("%.10lf\n",A);
				else if(z==j)printf("%.10lf\n",B);
				else if(z==k)printf("%.10lf\n",C);
				else puts("0");
			}
			return 0;
		}
	}
	return 0;
}