2019南京区域赛

K.Triangle

思路

先用海伦公式求出面积的一半

$$\frac{1}{2}S=\sqrt{p(p-l1)(p-l2)(p-l3)}$$

然后通过正弦函数和余弦定理求出夹角$\alpha$
这样就可以通过公式

$$\frac{1}{2}*sin\alpha*x*b=\frac{1}{2}S$$

这样就能够求出x偏移量，通过偏移量和边上的两个点就够求出答案了

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1)
struct Point{
	ll x,y;
	bool operator < (const Point a)
	{
		return x<a.x;
	 } 
}pp[3];
struct line{
	Point s,t;
};
bool in(ll x2,ll y2,ll x3,ll y3,ll x0,ll yy0){
  if((x0-x2)*(y3-y2)==(x3-x2)*(yy0-y2)&&min(x2,x3)<=x0&&x0<=max(x2,x3)&&min(y2,y3)<=yy0&&yy0<=max(y2,y3)){
          return true;    
		  }else{        
		  return false;   
	}
}

int judge(line l1,line l2,line l3,Point p)
{
	if(in(l1.s.x,l1.s.y,l1.t.x,l1.t.y,p.x,p.y))return 1;
	if(in(l2.s.x,l2.s.y,l2.t.x,l2.t.y,p.x,p.y))return 2;
	if(in(l3.s.x,l3.s.y,l3.t.x,l3.t.y,p.x,p.y))return 3;
	return -1;
}
double dis(Point a,Point b)
{
   return sqrt(1ll*(b.x-a.x)*(b.x-a.x)+1ll*(b.y-a.y)*(b.y-a.y));	
}
void getans(Point s,Point t,double x)
{
	printf("%.12lf %.12lf\n",s.x+(t.x-s.x)*x/dis(s,t),s.y+(t.y-s.y)*x/dis(s,t));
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)
	{
	ll x1,x2,x3,y1,y2,y3,px,py;
	scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3,&px,&py);
	if(px==x1&&py==y1)
	{
		printf("%.12lf %.12lf\n",1.0*(x2+x3)/2,1.0*(y2+y3)/2);
		continue;
	}
	if(px==x2&&py==y2)
	{
		printf("%.12lf %.12lf\n",1.0*(x1+x3)/2,1.0*(y1+y3)/2);
		continue;
	}
	if(px==x3&&py==y3)
	{
		printf("%.12lf %.12lf\n",1.0*(x2+x1)/2,1.0*(y2+y1)/2);
		continue;
	}
	 pp[0]={x1,y1};
	 pp[1]={x2,y2};
	 pp[2]={x3,y3};
	sort(pp,pp+3);
	Point p1=pp[0];
	Point p2=pp[1];
	Point p3=pp[2];
	Point p = {px,py};
	line l1 = line{p1,p2};
	line l2 = line{p2,p3};
	line l3 = line{p1,p3};
	double lenl1 = dis(l1.s,l1.t);
	double lenl2 = dis(l2.s,l2.t);
	double lenl3 = dis(l3.s,l3.t);
	double P=(lenl1+lenl2+lenl3)/2;
	double S=sqrt(P*(P-lenl1)*(P-lenl2)*(P-lenl3));
	int l = judge(l1,l2,l3,p);
	if(l==-1){printf("-1\n");continue;}
	else if(l==1)
	{
		if(dis(p1,p)>lenl1/2)
		{
			double d = dis(p,p1);
			double x = S/(d*(sin(acos((lenl1*lenl1+lenl3*lenl3-lenl2*lenl2)/(2*lenl1*lenl3)))));
			getans(p1,p3,x);
		}
		else
		{
			double d = dis(p,p2);
			double x = S/(d*(sin(acos((lenl1*lenl1+lenl2*lenl2-lenl3*lenl3)/(2*lenl1*lenl2)))));
			getans(p2,p3,x);
		}
	}
	else if(l==2)
	{
		if(dis(p,p2)>lenl2/2)
		{
			double d = dis(p2,p);
			double x = S/(d*(sin(acos((lenl1*lenl1+lenl2*lenl2-lenl3*lenl3)/(2*lenl1*lenl2)))));
			getans(p2,p1,x);
		}
		else
		{
			double d = dis(p,p3);
			double x = S/(d*(sin(acos((lenl2*lenl2+lenl3*lenl3-lenl1*lenl1)/(2*lenl2*lenl3)))));
			getans(p3,p1,x);
		} 
	}
	else if(l==3)
	{
		if(dis(p,p3)>=lenl3/2)
		{
			double d = dis(p,p3);
			double x = S/(d*(sin(acos((lenl2*lenl2+lenl3*lenl3-lenl1*lenl1)/(2*lenl2*lenl3)))));
			getans(p3,p2,x);
		}
		else
		{
			double d = dis(p,p1);
			double x = S/(d*(sin(acos((lenl1*lenl1+lenl3*lenl3-lenl2*lenl2)/(2*lenl1*lenl3)))));
			getans(p1,p2,x);
		}
	}
    }
}

H. Prince and Princess

思路

实际上这道题只有第三个发问是有用的，我们只需要问(b+c)*2+1个人第三个问题，出现最多的就是公主所在之地，但是要特判(1,0,0)的时候答案为0.

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a==1&&b==0&&c==0)printf("YES\n0\n");
    else if(b==0&&c==0)printf("YES\n1\n");
    else if(a>b+c)printf("YES\n%d\n",(b+c)*2+1);
    else printf("NO\n");
}

A. A Hard Problem

思路

这题把1-n拆成两部分，一部分是
$\lceil \frac{n}{2} \rceil$,拿到这部分之后，根据鸽巢原理可以知道如果k在多1的话就一定可以找到倍数关系，答案就是$\lceil \frac{n}{2} \rceil+1$

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int ans = n/2;
		if(n%2!=0)ans++;
		printf("%d\n",ans+1);
	}
 }