一、有多少种划分方式
给定一个长度为N的数组，数组中每一项都是[1,10000]且没有重复元素，现在把它划分为若干个子序列，要求：
- 每个子序列都是等差数列或者等比数列
- 每个子序列的长度不小于3
- 子序列中的元素在原数组中可以不相邻，但是下标一定是升序
问有多少种划分方式？
这题我能想到的就是暴力。三重for循环确定一个子序列的基调，然后尽量长地扩展出一个长数组，对长数组外的元素递归求解。
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
int[] how = new int[(int) 1e4 + 7];
//获取i,j,k三个首项确定的子序列，用a减去这些元素即得下次需要处理的元素
List<Integer> get(int i, int j, int k, List<Integer> a) {
List<Integer> b = new LinkedList<>();
boolean dengbi = (a.get(j) * a.get(j) == a.get(i) * a.get(k));
double a0 = a.get(i), d;
if (dengbi) {
d = ((double) a.get(j)) / a.get(i);
} else {
d = a.get(j) - a.get(i);
}
for (int t = k + 1; t < a.size(); t++) {
if (t == i || t == j || t == k) continue;
if (dengbi) {
if (a.get(t) != Math.pow(d, a.size()) * a0) {
b.add(a.get(t));
}
} else {
if (a.get(t) != a0 + b.size() * d) {
b.add(a.get(t));
}
}
}
return b;
}
int go(List<Integer> a) {
if (a.size() < 3) return 0;
int s = 0;
//三重for循环遍历首项
for (int i = 0; i < a.size(); i++) {
for (int j = i + 1; j < a.size(); j++) {
for (int k = j + 1; k < a.size(); k++) {
if (a.get(j) * 2 == a.get(i) + a.get(k) || a.get(j) * a.get(j) == a.get(i) * a.get(k)) {
List<Integer> next = get(i, j, k, a);
int sz = a.size() - next.size();
if (sz == a.size()) {
s += how[sz];
} else {
s += how[sz] * go(next);
}
}
}
}
}
return s;
}
Main() {
//初始化how数组，它表示一个尽量等比数列或者等差数列有多少种划分方法
how[0] = how[1] = how[2] = 0;
how[3] = 1;
for (int i = 4; i < how.length; i++) {
int s = 0;
for (int j = 3; j < i; j++) {
s += how[i - j];
}
how[i] = s;
}
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < a.length; i++) a[i] = cin.nextInt();
List<Integer> alink = new LinkedList<>();
for (int i = 0; i < a.length; i++) alink.add(a[i]);
System.out.println(go(alink));
}
public static void main(String[] args) {
new Main();
}
}
二、计算几何
给定一个点，一个多边形（可能非凸），问点是否在多边形内，距离多边形的最短距离是多少？
这道题基本上是套路题。但是只对了80%，不知何故。
首先，判断点是否在多边形内部，使用射线法，从当前点向一个方向发出一条射线，求射线跟多边形边的交点的个数，如果为奇数个说明在多边形内部。
其次，求点到多边形的最短距离，直接求点到多边形所有线段的最短距离即可。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
public static boolean IsPtInPoly(Point point, List<Point> pts) {
int N = pts.size();
boolean boundOrVertex = true; //如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
int intersectCount = 0;//cross points count of x
double precision = 2e-10; //浮点类型计算时候与0比较时候的容差
Point p1, p2;//neighbour bound vertices
Point p = point; //当前点
p1 = pts.get(0);//left vertex
for (int i = 1; i <= N; ++i) {//check all rays
if (p.equals(p1)) {
return boundOrVertex;//p is an vertex
}
p2 = pts.get(i % N);//right vertex
if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {//ray is outside of our interests
p1 = p2;
continue;//next ray left point
}
if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {//ray is crossing over by the algorithm (common part of)
if (p.y <= Math.max(p1.y, p2.y)) {//x is before of ray
if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {//overlies on a horizontal ray
return boundOrVertex;
}
if (p1.y == p2.y) {//ray is vertical
if (p1.y == p.y) {//overlies on a vertical ray
return boundOrVertex;
} else {//before ray
++intersectCount;
}
} else {//cross point on the left side
double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;//cross point of y
if (Math.abs(p.y - xinters) < precision) {//overlies on a ray
return boundOrVertex;
}
if (p.y < xinters) {//before ray
++intersectCount;
}
}
}
} else {//special case when ray is crossing through the vertex
if (p.x == p2.x && p.y <= p2.y) {//p crossing over p2
Point p3 = pts.get((i + 1) % N); //next vertex
if (p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)) {//p.x lies between p1.x & p3.x
++intersectCount;
} else {
intersectCount += 2;
}
}
}
p1 = p2;//next ray left point
}
if (intersectCount % 2 == 0) {//偶数在多边形外
return false;
} else { //奇数在多边形内
return true;
}
}
double dis(Point x, Point y) {
return Math.hypot(x.x - y.x, x.y - y.y);
}
double dis(Point x, Point y, Point z) {//x到线段yz的距离
double space = 0;
double a, b, c;
a = dis(y, z);// 线段的长度
b = dis(x, y);// (x1,y1)到点的距离
c = dis(x, z);// (x2,y2)到点的距离
if (c <= 0.000001 || b <= 0.000001) {
space = 0;
return space;
}
if (a <= 0.000001) {
space = b;
return space;
}
if (c * c >= a * a + b * b) {
space = b;
return space;
}
if (b * b >= a * a + c * c) {
space = c;
return space;
}
double p = (a + b + c) / 2;// 半周长
double s = Math.sqrt(p * (p - a) * (p - b) * (p - c));// 海伦公式求面积
space = 2 * s / a;// 返回点到线的距离（利用三角形面积公式求高）
return space;
}
long get(Point p, List<Point> a) {
double ans = Double.MAX_VALUE;
for (Point i : a) {
ans = Math.min(dis(i, p), ans);
}
for (int i = 0; i < a.size(); i++) {
ans = Math.min(ans, dis(p, a.get(i), a.get((i + 1) % a.size())));
}
return Math.round(ans);
}
Main() {
Scanner cin = new Scanner(System.in);
double mexy[] = Arrays.stream(cin.next().split(",")).mapToDouble(Double::parseDouble).toArray();
Point me = new Point(mexy[0], mexy[1]);
double aa[] = Arrays.stream(cin.next().split(",")).mapToDouble(Double::parseDouble).toArray();
List<Point> a = new ArrayList<>(aa.length >> 1);
for (int i = 0; i < aa.length / 2; i++) {
a.add(new Point(aa[i * 2], aa[i * 2 + 1]));
}
boolean x = IsPtInPoly(me, a);
if (x) {
System.out.println("yes,0");
} else {
long ans = get(me, a);
if (ans == 0) System.out.println("yes,0");
else System.out.println("no," + ans);
}
}
public static void main(String[] args) {
new Main();
}
}