网站建设服务器价格,深圳宝安有多少个区,全网营销思路,字体设计转换器计算被直线划分区域
在笛卡尔坐标系#xff0c;存在区域[A,B],被不同线划分成多块小的区域#xff0c;简单起见#xff0c;假设这些不同线都直线并且不存在三条直线相交于一点的情况。 img
那么#xff0c;如何快速计算某个时刻#xff0c;在 X 坐标轴上[ A#xff0c;…计算被直线划分区域
在笛卡尔坐标系存在区域[A,B],被不同线划分成多块小的区域简单起见假设这些不同线都直线并且不存在三条直线相交于一点的情况。 img
那么如何快速计算某个时刻在 X 坐标轴上[ A B] 区间面积被直线划分成多少块
A轴平行坐标Y轴A (x1)
B轴平行坐标Y轴, B(x 20);
输入描述
输入采用多行输入一行4个数据分别表示两个坐标点一行一条直线
1420,100 - 表两个点点t1的坐标为1,4点t2坐标为20,100
输出描述
输出为整数表示被输入线段划分的面积个数
示例1
输入
1,37,20,4
1,7,20,121输出
4备注
AB之间的线段不平行于Y轴
思路
几何题当两条线在这一区域内不相交时区域空间增加1当两条线的交点在这一区域内时空间增加2所以我们判断交点是否在区域内即可
代码 public static void main(String[] args) {Scanner in new Scanner(System.in);Listint[] edges new ArrayList();int res 1;while(in.hasNextLine()){String inputLine in.nextLine();if (inputLine.isEmpty()) {break; // 如果输入为空行退出循环}res1;String[] line inputLine.split(,);if(line[0]) continue;int[] nodes new int[4];for(int i0;i4;i){nodes[i] Integer.parseInt(line[i]);}for(int[] edge:edges){double x getIntersection(nodes[0],nodes[1],nodes[2],nodes[3],edge[0],edge[1],edge[2],edge[3]);if(x20 x1) res1;}edges.add(nodes);}System.out.println(res);}static double getIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){double k1 (y1-y2)/(x1-x2);double b1 y1 - k1*x1;double k2 (y4-y3)/(x4-x3);double b2 y3 - k2*x3;double x (b2-b1)/(k1-k2);return x;}最佳面试策略
小明最近在找工作收到了许多面试邀约可参加的面试由interviews 数组表示其中 interviews[i] [startTimei, endTimei, possibilityi]表示第 i 个面试在 startTimei 开始endTimei 结束面试成功的可能性是 possibilityi该值越大通过面试的可能性越大由于精力限制小明最多可以参加 k 场面试。
小明同一时间只能参加一场面试如果要参加某场面试必须完整参加这场面试才可能通过面试即不能同时参加一个开始时间和另一个结束时间相同的两场面试。
请给出小明面试成功可能性的最大和。
示例1
输入
[[1,2,3],[3,4,2],[2,4,4]],2输出
5说明
小明参加 [1, 2, 3] [3, 4, 2] 两场面试面试通过可能性的和为 3 2 5示例2
输入
[[1,2,3],[3,4,2],[2,4,6]],2输出
6说明
只参加面试 [2, 4, 6]面试通过的可能性的和最大为 6
思路 对于这道题我们先定义dp的状态dp[i][j]为面对i这个时间段的面试已经面试了j次决策后的最大可能值
先对interviews根据左端的值进行排序。
然后从后往前遍历interviews使用二分搜索的方法算出当前面试i的下一场面试然后我们逐次消耗面试次数记录消耗j次面试机会的最大可能值与进行下一次面试的值做比较得到最终的最大值
注意这里我们记录了dp[i1][j]的值就是当这个可能值 i加上后面的面试的可能值时会保留更大的那个可能值的结果
代码
import java.util.Arrays;public class algorithm {public static void main(String[] args) {int[][] s { {1,2,3},{3,4,2},{2,4,6} };System.out.println(maxValue(s,2));}public static int maxValue(int[][] interviews,int k){Arrays.sort(interviews,(a,b)-a[0]-b[0]);int n interviews.length;int[][] dp new int[n1][k1];for(int in-1;i0;i--){int li,rn;while (lr){int mid (lr)1;if(interviews[i][1]interviews[mid][0]) rmid;else lmid1;}for(int j0;jk;j){dp[i][j] dp[i1][j];if(j0) dp[i][j] Math.max(dp[i][j],dp[r][j-1]interviews[i][2]);}}return dp[0][k];}}
星球间的最短通路
在一个遥远的银河中有N个星球编号从1到N这些星球之间通过星际门进行连接。每个星际门都连接两个星球并且可以双向通行。
每个星际门的开启需要消耗一定的能量这个能量由星际门上的数字表示。每个星际门上的数字都是唯一的。
现在由于某种原因所有的星际门都处于关闭状态。作为一个探索者你的任务是找出一种方式开启最少的星际门使得所有的星球都至少通过一个开启的星际门与其他星球连接。
给你一些可连接的选项 connections其中 connections[i] [Xi, Yi, Mi] 表示星球 Xi 和星球 Yi 之间可以开启一个星际门并消耗 Mi 能量。
计算联通所有星球所需的最小能量消耗。如果无法联通所有星球则输出-1。
示例1
输入
3,[[1, 2, 5], [1, 3, 6], [2, 3, 1]]输出
6备注
1 ≤ N ≤ 100
思路
使用克鲁斯卡尔算法求最小图这其中使用到了并查集的东西
代码
import java.util.Arrays;public class Main {int[] fa;void init(int n){fa new int[n];for(int i0;in;i) fa[i] i;}int find(int x){return x fa[x]? x: (fa[x] find(fa[x] ));}void union(int x,int y){fa[find(x)] find(y);}public int minimumCost(int n,int[][] connections){init(20000);Arrays.sort(connections,(a,b)-a[2]-b[2]);int ans 0;for(int[] arr:connections){int a arr[0],barr[1],warr[2];if(find(a)!find(b)){union(a,b);answ;}}return ans;}public static void main(String[] args) {Main a new Main();int[][] s {{1, 2, 5}, {1, 3, 6}, {2, 3, 1}};System.out.println(a.minimumCost(3,s));}
}
