题解篇-C6

本文图片可能有时加载不出来，主要github不支持数学公式，我就只能放图，但是github的图片也功能经常出现问题，所以大家体谅一下

A-A*B

题目描述

计算A*B

时间限制：1000ms 内存限制：65536KB

输入

多组数据输入

两行两个大整数A和B，A和B保证小于等于50000位。

输出

每组数据输出一行，A*B的值

输入样例

1	12345678987654321 98765432123456789

输出样例

1	1219326320073159566072245112635269

提示

可能有负数哦

分析

首先如果大家有上课听讲了一丢丢并且下课很认真找过板子的话，肯定还是很容易找到FFT的板子的，这样就只用改负号了，如果没有并且想看下分析的可以往下阅读，当然可以直接看代码快乐AC。

首先我们如果用普通乘法采用竖式计算的方法的话时间复杂度为O(n²)，肯定是过不了的，所以我们采用FFT算法的话，我们可以降到O(nlogn)的复杂度，就可以随意过了。步入正题，说清楚这个板子不太容易。首先是多项式的两种表示方法——系数表示和点值表示。首先我们常见的多项式都是这样的A=a₀+a₁x+a₂x²+……+a_n-1x^n-1，然后系数表示法就是用一个n维向量来表示A={a₀,a₁,…a_n-1}，这样肯定能一一对应的表示多项式；然后是点值表示法，我们只用确定n个点x_i和其对应的A，就肯定可以反推出A的多项式表达，所以点值表示法就是由n个点组成的{(0,A(0)),(1,A(1)),…,(n-1,A(n-1))}，这n个点可以随机取，并且该表示肯定也可以一一对应的表示多项式的，然后我们表示出A和B之后想要求出C，那C的点值表达肯定就是从A和B中取2n个点乘起来，然后也能得到点值表达，但是时间复杂度为O(n²)这样肯定不行。我们下面要做的就是把多项式从系数表达转换为点值表达，然后再转换回去，这些过程的时间复杂度都是低于O(nlogn)的。

然后我们就说一下复数的知识，首先任何复数z都能表示成为一个向量z=r(cosθ+isinθ)，其中r为z的模长，θ为向量与x轴的夹角，称为幅角。根据欧拉公式：e^iθ=cosθ+isinθ，所以z=r*e^iθ，所以可以推出(cosθ+isinθ)^α=(cosαθ+isinαθ) ，这就是棣莫弗公式。然后是在方程xⁿ=1中，满足这个方程的解一共有n个，这n个解构成了1的n次单位根。并且这n个根中至少存在一个根w_n使得w_n的1~n次方刚好就对应这些n次单位根，这样的w_n就称为本原根，即这些n次单位根可以表示为w_n⁰,w_n¹,w_n²,…,w_n^n-1，并且这些数的n次方都为1，因此由棣莫弗公式我们可以得到一个通用(本原根可能不止一个)本原根w_n= cos(2π/n)+i*sin(2π/n)。

然后介绍DFT(离散傅里叶变换)，我们之前所说的点值表示中x_i的选取是随机的。而DFT的奇妙则是n个点取的就是上文所说的n次单位根。我们的A(x)可以表示为A(x)= ∑_jⁿ⁻¹(a_j∗x^j)(j从0开始)，然后x取n个单位根，即表示为y_k=A(w_n^k)=∑_jⁿ⁻¹(a_j*(w_n^k)^j)(j从0开始，0<=k<=n-1)，这个数用y表示的话就是y={y₀,y₁,y₂, … ,y_n-1}。所以我们完成了从系数表示到点值表示转化的过程，只是这里的时间复杂度太高，我们不能采用。

然后我们再说FFT(快速傅里叶变换)，FFT本质也是把多项式的系数表达转换为点值表达，只不过时间复杂度更低。首先构造两个式子(A右上角那个0和1不是指数的意思，只是一个标号)：

A⁰(x)=a₀+a₂x+a₄x²+…+a_n-2x^n/2-1
A¹(x)=a₁+a₃x+a₅x²+…+a_n-1x^n/2-1

能够知道的是A(x)=A⁰(x²)+x*A¹(x²)，所以DFT问题就转化为了A⁰和A¹在(w_n⁰)²,(w_n¹)²,(w_n²)²,…,(w_n^n-1)²这些点上的求值问题，这样一直分裂下去，就是分治的思想就能解决问题了，并且时间复杂度在O(nlogn)内。

然后是如何递归的问题，虽然已经找到了分治的方法，但是转化后的问题并不相同，而是多了一个平方。我们的处理方法还是借用棣莫弗公式，转化后即得到w_αn^αk=w_n^k，所以问题里的(w_n⁰)²,(w_n¹)²,(w_n²)²,…,(w_n^n-1)²就转化为了w_n/2⁰,w_n/2¹,w_n/2²,…,w_n/2^n-1，所以只要每次处理子问题的时候替换一下本原根，就让子问题和原问题完全一样了。由于在口头上说不是那么容易理解，下面举一个n=4的例子：

y₀=A(w₄⁰)=A⁰((w₄⁰)²)+w₄⁰*A¹((w₄⁰)²)，y₁=A(w₄¹)=A⁰((w₄¹)²)+w₄¹*A¹((w₄¹)²)；

y₂=A(w₄²)=A⁰((w₄²)²)+w₄²*A¹((w₄²)²)，y₃=A(w₄³)=A⁰((w₄³)²)+w₄³*A¹((w₄³)²)；

根据上文提到的借用棣莫弗公式从而转换的方法，从而得到：

y₀=A(w₄⁰)=A⁰(w₂⁰)+w₄⁰*A¹(w₂⁰)，y₁=A(w₄¹)=A⁰(w₂¹)+w₄¹*A¹(w₂¹)；

y₂=A(w₄²)=A⁰(w₂²)+w₄²*A¹(w₂²)，y₃=A(w₄³)=A⁰(w₂³)+w₄³*A¹(w₂³)；

再经过一些简单的公式变换(w_n^k+n/2=w_n^k*w_n^n/2=-w_n^k(可以想想为何是-1)和w_n^k+n=w_n^k*w_nⁿ=w_n^k)，得到

y₀=A(w₄⁰)=A⁰(w₂⁰)+w₄⁰*A¹(w₂⁰)，y₁=A(w₄¹)=A⁰(w₂¹)+w₄¹*A¹(w₂¹)；

y₂=A(w₄²)=A⁰(w₂⁰)-w₄⁰*A¹(w₂⁰)，y₃=A(w₄³)=A⁰(w₂¹)-w₄¹*A¹(w₂¹)；

然后这样就能很简单快速的得出y的点值表达{y₀,y₁,y₂, … ,y_n-1}啦，时间也是O(nlogn)。

但是我们求出了所需要得结果C多项式的点值表达后，怎么算出C的系数表达呢。我们先构造一个范德蒙矩阵V(有w的那个矩阵)如下

这里我们可以记作y=V*a，同时观察这个V其中的元素，对于第k行第j列的元素，它的值为w_n^kj。我们FFT所求即求出了V，我们现在要把点值表达变回系数表达，也就是FFT的逆过程。对于这个也就是求a，转换一下上方的式子就是a=V^-1*y，而对于V^-1这个矩阵来说，它第j行第k列的元素，则是w_n^-kj/n(这里就不证明了，大家可以自己查阅)。

然后我们再考虑I_n=V*V^-1这个矩阵，考虑该矩阵中第j行第j’列的元素：

然后我们还需要一个引理：对任意大于等于1的整数n和不能被n整除的非负整数k，有：(证明也在下方)

也就是一个等比数列求和的过程，然后我们就能发现上面考虑的I_n矩阵中的j行j‘列元素在j!=j’的时候为0，相等的时候为1。所以我们就能根据a=V^-1*y得到以下式子：(下方也放上上文求出的y的式子)

所以我们在计算逆FFT时，就把a和y的位置互换，再用w_n^-1代替w_n¹，并把结果除以n就可以了。时间复杂度也是一样的，通过FFT和逆FFT的运用就能把次数界为 n 的多项式在其系数表示与点值表示之间来回进行转换。从而算出大数乘法了。

好了上面就是纯数学的推导部分，阅读起来应该不是很难(毕竟我这个cj都能理解)，然后再讲讲怎么具体应用于大数乘法。其实也很简单，首先运用FFT将A和B的系数表示转换为点值表示，然后将他们相乘得到C的点值表示，最后通过逆FFT将C转换为系数表示，输出答案就okkk了。然后先放代码吧。

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 150010
const double pi = 3.141592653;
char s1[N>>1], s2[N>>1];
double rea[N], ina[N], reb[N], inb[N];
int ans[N>>1];
void Swap(double *x, double *y)
{
    double t = *x;
    *x = *y;
    *y = t;
}
int Rev(int x, int len)
{
    int ans = 0;
    int i;
    for(i = 0; i < len; i++){
        ans<<=1;
        ans |= (x & 1);
        x>>=1;
    }
    return ans;
}//二进制的反转x->ans
//作用就是把这n个数分成我们想要的lgn个部分，且每个部分仅有两个待处理的，然后再处理
//不太明白的可以看看网上关于FFT中的二进制的翻转问题的博客啥的
void FFT(double *reA, double *inA, int n, bool flag)
{
    int s;
    double lgn = log((double)n) / log((double)2);//定义log(2)(n),也就是代表分裂次数
    int i;
    for(i = 0; i < n; i++){
        int j = Rev(i, lgn);
        if(j > i){
            Swap(&reA[i], &reA[j]);
            Swap(&inA[i], &inA[j]);
        }
    }
    for(s = 1; s <= lgn; s++){//共进行lgn次
        int m = (1<<s);
        double reWm = cos(2*pi/m), inWm = sin(2*pi/m);//本原根
        if(flag) inWm = -inWm;//对C来说就要转换为负的
        int k;
        for(k = 0; k < n; k += m){
            double reW = 1.0, inW = 0.0;
            int j;
            for(j = 0; j < m / 2; j++){
                int tag = k+j+m/2;//可以对照上文的公式看
                double reT = reW * reA[tag] - inW * inA[tag];
                double inT = reW * inA[tag] + inW * reA[tag];
                double reU = reA[k+j], inU = inA[k+j];
                reA[k+j] = reU + reT;
                inA[k+j] = inU + inT;
                reA[tag] = reU - reT;
                inA[tag] = inU - inT;
                double rew_t = reW * reWm - inW * inWm; 
                double inw_t = reW * inWm + inW * reWm; //这里实现迭代
                reW = rew_t;
                inW = inw_t;
            }
        }
    }
    if(flag){//对C来说需要除以n
        for(i = 0; i < n; i++){
            reA[i] /= n;
            inA[i] /= n;
        }
    }
}
 
int main()
{
#if 0
    //freopen("in.txt","r",stdin);
#endif
    while(~scanf("%s%s", s1, s2)){ 
    	int flag=0;
        memset(ans, 0 , sizeof(ans));
        memset(rea, 0 , sizeof(rea));
        memset(ina, 0 , sizeof(ina));
        memset(reb, 0 , sizeof(reb));
        memset(inb, 0 , sizeof(inb));//初始化
        int i, lent, len = 1, len1, len2;
        len1 = strlen(s1);
        len2 = strlen(s2);
        if(s1[0]=='-'){
        	for(int i=0;i<len1;i++){
        		s1[i]=s1[i+1];
			}
			len1--;
			flag^=1;
		}
		if(s2[0]=='-'){
        	for(int i=0;i<len2;i++){
        		s2[i]=s2[i+1];
			}
			len2--;
			flag^=1;
		}//符号的判断
        lent = (len1 > len2 ? len1 : len2);
        while(len < lent) len <<= 1;
        len <<= 1;// 保证长度为2的幂次，才能逐渐二分
        for(i = 0; i < len; i++){
            if(i < len1) rea[i] = (double)s1[len1-i-1] - '0';//将数组s1反转，并保存为double
            if(i < len2) reb[i] = (double)s2[len2-i-1] - '0';//将数组s2反转，并保存为double
            ina[i] = inb[i] = 0.0;
        }
        FFT(rea, ina, len, 0);//对A进行FFT
        FFT(reb, inb, len, 0);//对B进行FFT
        for(i = 0; i < len; i++){
            double rec = rea[i] * reb[i] - ina[i] * inb[i];
            double inc = rea[i] * inb[i] + ina[i] * reb[i];
            rea[i] = rec; ina[i] = inc;
        }//获得C的点值表达
        FFT(rea, ina, len, 1);
        for(i = 0; i < len; i++)
            ans[i] = (int)(rea[i] + 0.4);//舍入
        for(i = 0; i < len; i++){
            ans[i+1] += ans[i] / 10;
            ans[i] %= 10;
        }//消除进位
        int len_ans = len1 + len2 + 2;
        while(ans[len_ans] == 0 && len_ans > 0) len_ans--;
        if(flag) printf("-");
        for(i = len_ans; i >= 0; i--)
            printf("%d", ans[i]);
        printf("\n");
    }
    return 0;
}

上文的代码我几乎都标注了，应该能够比较容易的看懂了

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

B-定向越野

题目描述

为了锻炼身体，某楠参加了一个定向越野比赛，定向越野是利用地图和指北针导航的一项竞技运动，通常由起点出发，在多个点标处打卡，再返回终点。但是非酋某楠的指北针居然是坏的，所以只能靠记住来时的方向和各个点的坐标来判断下一步。现在希望你能够帮忙判断下一步是左转还是右转。对于每次转弯输出一个字符，左转输出’L’，右转输出’R’，直走不输出。

时间限制：1000ms，内存限制：65536KB

输入

多组数据输入

每组数据第一行一个数n，n表示按顺序经历的点的数量，包括起点、各个点标以及终点。1<n<10000

接下来n行每行两个整数为点的坐标，均在INT范围内。

输出

每组数据一行，每次转弯的方向’L’或’R’，中间用空格分隔

输入样例

输出样例

R L R

分析

很明显的一道计算几何题，用叉积判断方向就可，需要注意的是如果走直线是不输出的。还有一个就是可能long long会超，如果先算乘法再算减法的话(就是把叉积的式子展开了分别算)，就需要用double来存，如果是先减再乘，longlong就能随意过了。

AC代码

#include<stdio.h>
#include<stdlib.h>
int main(){
	int n;
	int x[10005],y[10005];
	int i;
	while(~scanf("%d",&n)){
		for(i=0;i<n;i++){
			scanf("%d%d",&x[i],&y[i]);
		}
		for(i=1;i<n-1;i++){
			if(((long long)(x[i]-x[i-1])*(y[i+1]-y[i])-(long long)(x[i+1]-x[i])*(y[i]-y[i-1]))>0)
				printf("L ");
			else if(((long long)(x[i]-x[i-1])*(y[i+1]-y[i])-(long long)(x[i+1]-x[i])*(y[i]-y[i-1]))<0)
				printf("R ");
		}
		printf("\n");
	}
	return 0;
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

C-危机合约

题目描述

一天起床，你突然发现自己成为了整合运动的一员，作为火刀哥的手下前去探路。由于危机合约的特殊性，博士只能布置没有阻挡数的干员，每路过一个干员就会受到一次他的攻击，你的目的就是在不被干掉的情况下，从位于最左第一列某点的红色出生点走到位于最右某点的蓝色目的地。作为一个普通宿主士兵，你只能走向右上，右，右下三个格子。

时间限制：1000ms，内存限制：65536KB

输入

第一行n和m，表示地图有n行m列 (n,m<100)

第二行h，a和b，h表示你现有的血量，红色出生点在第0列a行，蓝色目的地在第m+1列b行(1<=a,b<=n)

接下来n行，每行m列，其中’*’表示这个点不能走，数字表示这个点上干员对你的伤害，范围0到9

输出

如果能够活着走到目的地，则输出剩余血量

如果已经死亡，则输出”doctor win”

输入样例

输出样例

分析

首先应该能看出这是一道dp的题目，所以就先分析怎么样dp吧。首先本人先想到的是对当前的血量进行dp(好像和大部分盆友想法不太一样)，dp[i][j]即代表在i行j列处的血量，并且还没有扣除当前应该扣除的血量，即已经走到了i行j列，只是还没扣血(不太理解的可以从代码来理解)，这样dp的好处呢就是不用管*格是否走不走得到，反正就往下走，走到*后再往下走就直接把血扣到负数即可。然后转移方程呢，就是走到当前格子的血量等于前一列那三个格子中剩余血量减去需要扣除的血量后最大的。如下

1	dp[i][j]=tmax(dp[i-1][j-1]-map[i-1][j-1],dp[i][j-1]-map[i][j-1],dp[i+1][j-1]-map[i+1][j-1])//tmax指三者中的最大值

一些需要注意的地方呢就是，首先初始化的问题，*的格子赋值为inf，dp的初始值赋值为-inf，map的初始值赋值为inf，因为要保证第一步走的时候的正确性，然后还要比所给的图多赋值一圈，才能保证在边缘的时候不会走错，然后a点的初始化就是dp[a][0]=h,map[a][0]=-inf，因为赋值都是inf和-inf并且还存在减法，数据的要求也是10⁹，所以把dp和map设置成long long比较安全。最后还有一个很坑的就是读入的问题了，scanf和getchar真的有毒，因为\r\n等诸多问题，所以还是建议用cin比较好。最后我在代码里也加一个其他dp的方法也能ac。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define inf 2147483647 
typedef long long ll;
ll dp[105][105];
ll dmax(ll a,ll b,ll c){
	if(a>=b&&a>=c) return a;
	if(b>=a&&b>=c) return b;
	if(c>=a&&c>=b) return c;
	return 0;
}
int main(){
	char c;
	ll map[105][105];
	int n,m;
	scanf("%d%d",&n,&m);
	int h,a,b;
	scanf("%d%d%d",&h,&a,&b);
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			dp[i][j]=-inf;
			map[i][j]=inf;
		}
	}
	dp[a][0]=h;
	map[a][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c!='*') map[i][j]=c-'0';
			else map[i][j]=inf;
		}
	}
	for(int j=1;j<=m+1;j++){
		for(int i=1;i<=n;i++){
			dp[i][j]=dmax(dp[i-1][j-1]-map[i-1][j-1],dp[i][j-1]-map[i][j-1],dp[i+1][j-1]-map[i+1][j-1]);
			
		}
	}
    /*for(int j=1;j<=m+1;j++){
		for(int i=1;i<=n;i++){
			dp[i][j]=dmin(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])+map[i][j];
		}
	}*/
    //这个dp对应的就是减少的生命值，初始化就是反的，并且最后的输出和判断doctor win也有点区别，还有就是求的是最小值，其实两个dp实际上是一样的
	if(dp[b][m+1]<=0) printf("doctor win");
	else printf("%lld",dp[b][m+1]);
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

D-不NAN的过河

题目描述

某楠也要过Zexal过的那条河，通过借助河中间的石砖过到河对岸去，这些石砖以直线排列。河的长度为L，当某楠走到或跨过坐标为L的点时，就算到达了河对岸。但是强迫症的某楠最多只能跨m次，请你计算某楠过河最长的一步最少是多少。注意从岸边迈向石头和从石头迈向岸边也算1步。

时间限制：1000ms，内存限制：65536KB

输入

多组数据输入

每组数据第一行有3个正整数L，n，m，L表示河的宽度，n表示有n个石砖，m表示某楠最多只能跨m步。(1≤L≤10⁹,1≤n≤10⁵,1≤m≤10⁵)

第二行有n个不同的正整数分别表示这n个石砖在数轴上的位置（所有相邻的整数之间用一个空格隔开。

输出

每组数据输出一个整数，表示某楠迈的最长一步的最小距离。

输入样例

1
2

5 2 3
1 3

输出样例

分析

首先看问题他要求最长一步的最小距离，肯定需要去判断，遍历判断肯定时间不太行，O(n²)肯定超了，所以我们就采用二分来枚举即可，时间是绰绰有余的。然后是怎么判断的问题了，便于理解，我们把a[0]设为0，a[n+1]设为L，然后判断的问题，肯定要让每一步跨的最大，所以就是贪心的思想。在遇到一步跨不到的石砖时才记录步数，然后将开始的地方置为当前石砖的前一块也就是a[i-1]，这样需要考虑的就是如果一步跨过了岸边，那它也会将开始的地方置为a[n]，所以最后一步就没有算上，所以我们cnt初始值设为1而不是0。还有一个很重要的就是，他没有说石砖是有序的，所以最开始需要排个序才行(这个bug太恶心)。

AC代码

#include<stdio.h>
#include<stdlib.h>
int a[100005];
int n,m,l,mid;
int cmp(void const *a,void const *b){
	int c,d;
	c=*(int *)a;
	d=*(int *)b;
	return c-d;
}
int check() {
	int cnt=1,pre=a[0];
	for(int i=1; i<=n+1; i++) {
		if(a[i]-pre>mid) {
			pre=a[i-1];
			cnt++;
			if(a[i]-pre>mid)
				return 0;
		}
	}
	if(cnt<=m) return 1;
	return 0;
}
int main() {
	while(~scanf("%d%d%d",&l,&n,&m)) {
		a[0]=0,a[n+1]=l;
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
		} 
		qsort(a,n+2,sizeof(int),cmp);
		int left=0,right=l,ans;
		while(left<=right) {
			mid=(left+right)/2;
			if(check()) ans=mid,right=mid-1;
			else left=mid+1;
		}
		printf("%d\n",ans);
	}
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

E-线段交点

题面

有两条线段，求线段的交点。

时间限制：1000ms 内存限制：65536KB

输入

多组输入数据

每组数据两行

每行两个整数x，y，分别表示一条线段的x坐标，y坐标(−100≤x,y≤100)

输出

每组数据输出一行，两个数表示交点的坐标，中间用空格隔开。如果没有交点，或者线段重合，输出none

输入样例

输出样例

1 2	0.50 0.50 none

分析

首先这道题就是一道数学题感觉，需要考虑的情况很多，考虑完全就能过了。步入正题，我们两条直线先设置为AB，CD，交点为O，叉积用cross()表示。首先肯定是判断能否相交，因为我们是根据叉积来判断的，所以相交的情况也会比较多一些。首先先看正常的相交，也就是相交点不在端点处。对应的条件就是cross(AC,AB)和cross(AD,AB)异号并且cross(CA,CD)和cross(CB,CD)异号即可。然后是AB端点和CD重合的情况，对应的条件就是cross(AC,AB)和cross(AD,AB)异号并且cross(CA,CD)和cross(CB,CD)积为0，当然还有相反的情况(CD端点和AB重合，条件就不说了)，然后是重合和平行的情况，即叉积cross(AB,CD)为0，这里面也有一种相交的情况即诸如这种A->B(C)->D情况，怎么讨论这种情况呢，如果AB的两个端点均在CD线段上，这肯定是重合，那这个情况怎么判断呢，我用的方法比较笨(应该会有更简便的方法的)，通过AC斜率和AD斜率相等并且A的x、y坐标在C和D的x、y坐标中间，对B也一样，然后就是这种重合情况。然后在这种情况之外如果存在一组端点(A和C及其他情况)重合的情况，则是相交了，这种情况的判断方法我用的也比较笨，即通过判断A是否和C或者D重合，以及B是否和C或者D重合，然后如果重合就说明相交了，并且在这里需要输出，因为正常算交点的方法没法算这种情况，这里输出应该比较容易，存在重合就直接输出坐标就好了。然后其他的情况都是none即可。这就是所有的情况了。前面几种都比较好实现，最后一个情况会麻烦一些(也可能是我的方法比较笨)。

然后再说一下怎么算交点的问题了。就是通过算出两个三角形ACD,BCD的面积，然后根据其比值求出AO比AB，然后求出向量OA，然后用A的坐标加上OA向量即得到O的坐标了，比较容易理解。

AC代码

#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
class Point{
	public: 
		double x,y;
		Point(double x=0, double y=0):x(x),y(y) {}
		Point operator + (Point p){
			return Point(x+p.x,y+p.y);//重定义加法，点的加法即坐标相加，也可能是点和向量相加 
		}
		Point operator - (Point p){
			return Point(x-p.x,y-p.y);//重定义减法，点的减法即坐标相减 
		}
		Point operator * (double a){
			return Point(a*x,a*y);//重定义乘法，点乘常数即以坐标乘常数 
		}
}; 
typedef Point Vector;//因为向量Vector也能用X,Y表示
int flag; 
struct Segment{ //Segment 线段
	Point p1,p2;
};
double cross(Vector a, Vector b) {//向量的外积 
	return a.x*b.y - a.y*b.x;
}
double crossx(Point p1,Point p2,Point q1,Point q2){//也是外积不过是具体的点之间的 
	return (p1.x-p2.x)*(q1.y-q2.y)-(p1.y-p2.y)*(q1.x-q2.x);//p1p2 x q1q2 
}
bool issame(Point P1,Point P2,Point Q1,Point Q2) {
	if((P1.x==Q1.x&&P1.y==Q1.y)&&(!(P2.x==Q2.x&&P2.y==Q2.y))) { //P1=Q1
		printf("%lf %lf\n",P1.x,P1.y);
		return true;
	} else if((!(P1.x==Q1.x&&P1.y==Q1.y))&&(P2.x==Q2.x&&P2.y==Q2.y)) { //P2=Q2
		printf("%lf %lf\n",P2.x,P2.y);
		return true;
	} else if((P2.x==Q1.x&&P2.y==Q1.y)&&(!(P1.x==Q2.x&&P1.y==Q2.y))) { //P2=Q1
		printf("%lf %lf\n",P2.x,P2.y);
		return true;
	} else if((!(P2.x==Q1.x&&P2.y==Q1.y))&&(P1.x==Q2.x&&P1.y==Q2.y)) { //P1=Q2
		printf("%lf %lf\n",P1.x,P1.y);
		return true;
	} else return false;
}
bool isch(Point P1,Point P2,Point Q1,Point Q2){ 
	if(//存在两个端点均与另一线段重合
		((P2.y-Q1.y)*(Q1.x-P1.x)==(Q1.y-P1.y)*(P2.x-Q1.x)&&(((P1.x<=Q1.x)&&(P2.x>=Q1.x))||((P1.x>=Q1.x)&&(P2.x<=Q1.x)))&&(((P1.y<=Q1.y)&&(P2.y>=Q1.y))||((P1.y>=Q1.y)&&(P2.y<=Q1.y)))&&
		(P2.y-Q2.y)*(Q2.x-P1.x)==(Q2.y-P1.y)*(P2.x-Q2.x)&&(((P1.x<=Q2.x)&&(P2.x>=Q2.x))||((P1.x>=Q2.x)&&(P2.x<=Q2.x)))&&(((P1.y<=Q2.y)&&(P2.y>=Q2.y))||((P1.y>=Q2.y)&&(P2.y<=Q2.y))))||
		((Q2.y-P1.y)*(P1.x-Q1.x)==(P1.y-Q1.y)*(Q2.x-P1.x)&&(((Q1.x<=P1.x)&&(Q2.x>=P1.x))||((Q1.x>=P1.x)&&(Q2.x<=P1.x)))&&(((Q1.y<=P1.y)&&(Q2.y>=P1.y))||((Q1.y>=P1.y)&&(Q2.y<=P1.y)))&&
		(Q2.y-P2.y)*(P2.x-Q1.x)==(P2.y-Q1.y)*(Q2.x-P2.x)&&(((Q1.x<=P2.x)&&(Q2.x>=P2.x))||((Q1.x>=P2.x)&&(Q2.x<=P2.x)))&&(((Q1.y<=P2.y)&&(Q2.y>=P2.y))||((Q1.y>=P2.y)&&(Q2.y<=P2.y))))
	)
		return true;
	return false;
}
bool judge(Point p1,Point p2,Point q1,Point q2){//判断是否相交 
	if(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)<0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)<0) 
		return true;//正常相交 
	else if((crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)<0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)==0)||
			(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)==0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)<0))
		return true;//存在一端点在另一条线段上而不是端点处的相交 
	else if(crossx(p1,q1,p1,p2)*crossx(p1,q2,p1,p2)==0&&crossx(q1,p1,q1,q2)*crossx(q1,p2,q1,q2)==0){//共线 
		if(isch(p1,p2,q1,q2)) return false; 
		else if(issame(p1,p2,q1,q2)){//存在一组端点重合 
			flag=1;//不是正常相交，需要自己算，之后就不算 
			return true;
		}
		else return false;
	}
	return false;		
}
Point getCrossPoint(Segment s1,Segment s2){
	Vector base;//向量
	base=s2.p2-s2.p1; 
	double d1=fabs(cross(base,s1.p1-s2.p1));
	double d2=fabs(cross(base,s1.p2-s2.p1));//算三角形面积，只是没有除以2 
	double t=d1/(d1+d2);//面积之比等于线段之比，可理解为t=AO/(AO+BO) 
	return s1.p1+(s1.p2-s1.p1)*t;//通过A点坐标加上向量OA然后求得O点坐标 
}
int main() {
	Segment s1,s2;
	Point p;
	while(~scanf("%lf%lf%lf%lf",&s1.p1.x,&s1.p1.y,&s1.p2.x,&s1.p2.y)) {
		flag=0;
		scanf("%lf%lf%lf%lf",&s2.p1.x,&s2.p1.y,&s2.p2.x,&s2.p2.y);
		if(!judge(s1.p1,s1.p2,s2.p1,s2.p2)) printf("none\n");
		else {
			if(!flag) {
				p=getCrossPoint(s1,s2);//交点坐标 
				printf("%lf %lf\n",p.x,p.y);
			}
		}
	}
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

F-直线

题面

二维平面上有n个黑点m个白点，现在请问是否存在一条直线使得所有的黑点白点分别在直线两侧（黑点都在一侧，白点都在另一侧）。

时间限制：1000ms 内存限制：65536KB

输入

对于每组数据：

第一行两个正整数n、m。(1≤n,m≤100)

接下来n行，每行两个正整数x,y，表示一个黑点的xy坐标(1≤x,y≤1000)

接下来m行，每行两个正整数x,y，表示一个白点的xy坐标(1≤x,y≤1000)

输出

每组数据输出一行，存在输出YES，否则输出NO

输入样例

输出样例

1
2

YES
NO

分析

从题目来看可以比较容易可以看出是一道凸包的题目，即黑色点的凸包和白色点的凸包是否存在交点，存在，则不存在题中所说的直线，反之亦然。重点就是如何判断凸包是否相交呢。凸包相交也就分为两种情况，一种是一个凸包的点是否被另一凸包包含，包含并且不是全部的点被包含(需要特判一下)则肯定相交，第二种是两个凸包的边是否相交(比如两个三角形组成六芒星的图，点都不互相包含，但是凸包相交)。需要注意的就是，是否凸包被完全包含，以及凸包的点在另一个凸包的边的上。具体的怎么判断算法我就不多介绍了(有板子就好了)，大家可以看AC代码(网上找的板子)自己理解一下，我能看懂的地方都给大家标注了，但是很多具体的算法(比如判断边相交)我也没怎么详细看懂(不好意思，能力有限)。

AC代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
class Point {
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(Point a) {
        return Point(a.x + x, a.y + y);
    }
    Point operator-(Point a) {
        return Point(x - a.x, y - a.y);
    }
    bool operator<(const Point &a) const {
        if (x == a.x)
            return y < a.y;
        return x < a.x;
    }
    bool operator==(const Point &a) const {
        if (fabs(x - a.x) < eps && fabs(y - a.y) < eps)
            return 1;
        return 0;
    }
    double length() {
        return sqrt(x * x + y * y);
    }
};
typedef Point Vector;
double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}//叉积
double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}//点积
bool isclock(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) < -eps)
        return true;
    return false;
}//判断平行也就是夹角很小很小

double getDistance(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

typedef vector<Point> Polygon;
Polygon Andrew(Polygon s){
    Polygon u,l;
    if(s.size()<3) return s;
    sort(s.begin(), s.end());//根据x坐标排序 
    u.push_back(s[0]);
    u.push_back(s[1]);
    l.push_back(s[s.size()-1]);
    l.push_back(s[s.size()-2]);
    for(int i=2;i<s.size();++i){
        for(int n=u.size();n>=2&&!isclock(u[n-2],u[n-1],s[i]);--n){
            u.pop_back();
        }
        u.push_back(s[i]);
    }
    for(int i = s.size() - 3 ; i >= 0 ; --i) {
        for(int n = l.size() ; n >=2 && !isclock(l[n-2],l[n-1],s[i]); --n) {
            l.pop_back();
        }
        l.push_back(s[i]);
    }
    for(int i = 1 ; i < u.size() - 1 ; i++) l.push_back(u[i]);
    return l;
}

int dcmp(double x)  {
    if (fabs(x) <= eps)
        return 0;
    return x > 0 ? 1 : -1;
}

// 判断点在线段上
bool OnSegment(Point p, Point a1, Point a2) {
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}

// 判断线段相交
bool Intersection(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
            c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

// 判断点在凸包内
int isPointInPolygon(Point p, vector<Point> s) {
    int wn = 0, cc = s.size();
    for (int i = 0; i < cc; i++) {
        Point p1 = s[i];
        Point p2 = s[(i + 1) % cc];
        if (p1 == p || p2 == p || OnSegment(p, p1, p2)) return -1;
        int k = dcmp(cross(p2 - p1, p - p1));
        int d1 = dcmp(p1.y - p.y);
        int d2 = dcmp(p2.y - p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1;
    return 0;
}

void solve(Polygon s1, Polygon s2) {
    int c1 = s1.size(), c2 = s2.size();
    for(int i = 0; i < c1; ++i) {
        if(isPointInPolygon(s1[i], s2)) {//点是否包含
            printf("NO\n");
            return;
        }
    }
    for(int i = 0; i < c2; ++i) {
        if(isPointInPolygon(s2[i], s1)) {//同上
            printf("NO\n");
            return;
        }
    }
    for (int i = 0; i < c1; i++) {
        for (int j = 0; j < c2; j++) {
            if (Intersection(s1[i], s1[(i + 1) % c1], s2[j], s2[(j + 1) % c2])) {//线段相交判断
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
}

int main() {
    int n,m;
    while (cin>>n>>m){
        if(n==0&&m==0) break;
        Polygon s1,s2;
        for (int i=0;i<n;++i){
            double x1, x2;
            scanf("%lf%lf",&x1,&x2);
            s1.push_back(Point(x1, x2));
        }
        for (int i=0;i<m;++i){
            double x1, x2;
            scanf("%lf%lf",&x1,&x2);
            s2.push_back(Point(x1,x2));
        }
        if(s1.size()) s1=Andrew(s1);
        if(s2.size()) s2=Andrew(s2);
        solve(s1,s2);
    }
    return 0;
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。

G-逆序对

题面

逆序对的定义：在一个序列a中，如果i<j且 a_i>a_j 那么a_ia_j就是一个逆序对。

问相距最远的逆序对的距离（j-i）。如果没有逆序对，输出0。

时间限制：1000ms 内存限制：65536KB

输入

第一行一个数n，表示序列的长度。(1≤n≤10⁵)

接下来一行，n个整数，保证在int范围内

输出

一行一个数，表示最远逆序对的距离

输入样例

1
2

4
4 3 5 1

输出样例

分析

拿到这道题目能想到的第一个方法肯定就是暴力遍历，但是上机的时候粗略一看O(n²)会超就被我***的果断放弃了。。其实好像用不到O(n²)。步入正题，肯定是对每一个元素，找到其最远逆序对然后和max比较即可，最后输出max。但是怎么找最快呢，如果直接一步一步从前往后找，每一步还需要比较找出最大的，肯定就差不多O(n²)了，肯定过不了，但我们能发现的是，因为是找最远的，所以直接从后往前找，找到了一个就直接break就好了，因为求的是最远距离而不是差值，这样一来时间复杂度就比较乐观了。放上代码

AC代码

#include<stdio.h>
#include<stdlib.h>
struct node{
	int num;
	int distance;
}a[100005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i].num);
	}
	int max=-1;
	for(int i=0;i<n;i++){
		for(int j=n-1;j>=i+1;j--){
			if(a[j].num<a[i].num){
				a[i].distance=j-i;
				break; 
			}
		}
		if(a[i].distance>max) max=a[i].distance;
	}
	printf("%d",max);
}

如有谬误，请一定指出，本人争取马上修改，勿误导他人。