LCP 37. 最小矩形面积

我们发现对于对答案有影响的点只能有斜率相邻的线能够产生,因此我们可以把斜率相同的放在一组,相邻计算即可。

class Solution {
public:
static bool cmp(pair<int,int> x,const pair<int,int> y){
if(x.first!=y.first)return x.first<y.first;
else return x.second<y.second;
}
double minRecSize(vector<vector<int>>& lines) {
map<int,pair<int,int> > sq;//up down max
pair<int,int> st[123456];
int len=(int)lines.size();
for(int i=0;i<(int)lines.size();i++){
st[i]=make_pair(lines[i][0],lines[i][1]);
}
//cout<<st[0].first<<" "<<st[0].second<<endl;
sort(st,st+len,cmp);
double l,u,r,d;
l=u=r=d=0;
int count=0;
sq[st[0].first]=make_pair(st[0].second,st[0].second);
int last=st[0].first;
//cout<<sq[last].first<<" "<<sq[last].second<<endl;
for(int i=1;i<len;i++){
//cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
if(st[i].first==st[i-1].first){
int q=st[i].first;
int s=st[i].second;
if(sq[q].first<s)sq[q].first=s;
if(sq[q].second>s)sq[q].second=s;
//crazy
if(q==last)continue;
int dd1=st[i].second-sq[last].first;
int dd2=st[i].second-sq[last].second;
int qq=st[i].first-last;
double x1= -1.0*dd1/qq;
double x2=-1.0*dd2/qq;
double y1= st[i].first*x1+st[i].second;
double y2=st[i].first*x2+st[i].second;
if(count==0){
l=r=x1;
u=d=y1;
}
if(x1>r)r=x1;
if(x1<l)l=x1;
if(y1>u)u=y1;
if(y1<d)d=y1;
if(x2>r)r=x2;
if(x2<l)l=x2;
if(y2>u)u=y2;
if(y2<d)d=y2;
count++;
continue;
}
last=st[i-1].first;
//bug 
sq[st[i].first]=make_pair(st[i].second,st[i].second);
int dd1=st[i].second-sq[last].first;
int dd2=st[i].second-sq[last].second;
int q=st[i].first-last;
double x1= -1.0*dd1/q;
double x2=-1.0*dd2/q;
double y1= st[i].first*x1+st[i].second;
double y2=st[i].first*x2+st[i].second;
if(count==0){
l=r=x1;
u=d=y1;
}
if(x1>r)r=x1;
if(x1<l)l=x1;
if(y1>u)u=y1;
if(y1<d)d=y1;
if(x2>r)r=x2;
if(x2<l)l=x2;
if(y2>u)u=y2;
if(y2<d)d=y2;
count++;
}
if(!count)return 0;
else return fabs(u-d)*fabs(l-r);
}
};

 

推荐这些技术文章:

第十三届蓝桥杯大赛软件赛省赛C/C++大学B组真题(先占个位子有时间补)

A

B
C
D
E
F
G
H

(虽然贴代码也挺好但就是想试试新装的插件)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
const int N =...

C# 多点最小二乘法拟合平面算法

      /// <summary>
/// 实现三阶行列式求值计算
/// </summary>
/// <param name="x1"></param>
/// <param name="y1"></param>
/// <pa...

c++ pair对组创建

pair对组创建
功能描述:

成对出现的数据,利用对组可以返回两个数据

两种创建方式:

pair<type, type> p ( value1, value2 );
pair<type, type> p = make_pair( value1, value2 );

示例:

#include <string>

//对组创建
void test01()...

《九日集训》第十五轮 (第八讲) 二级指针

知识点
二级指针
int **myMalloc(int r, int c, int* returnSize, int** returnColumnSizes) {
int i;
int **ret = (int **)malloc( sizeof(int *) * r ); // (1)
*returnColumnSizes = (int *)malloc(...

最小生成树 边权非负

prim 算法
使用于领接矩阵版本
与dijkstra极其相似 只是更新的矩阵的数量不同
krukal算法
并查集
从小到大排序
一条边没有联通 就选择这条边
否则 如果联通就不选择这条边
求最大的边权最小
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace s...

2021年暑假康复性训练(Codeforces Round #731 (Div. 3))全题解

2021暑假康复性训练
Codeforces Round #731 (Div. 3)A Shortest Path with ObstacleB. Alphabetical StringsC. Pair Progr...

servlet response输出验证码

下面是两个工具代码:一个是生成验证码字符串,一个是生成验证码图片(它是基于生成验证码字符串类的)

public class CreateVerificationCode {
/**
* 验证码难度级别
*/
public enum SecurityCodeLevel {
Simple,
Medium,
Har...

前缀和差分(一维和二维)

一维前缀和

例题

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n,m;
int s[N],num[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
{
...

磊磊零基础打卡算法:day07 c++ 前缀和,二维前缀和

5.7

一维前缀和

主要思想;

初始化前缀和数

由于存在s[i] =s[i-1]+a[i];s是前缀和,a[i]是每一位的数;所以需要将i从1开始读入所有的数

for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + q[i];
}
//求区间的前缀和
cout << s[r] - s[l - 1] &...

矩形相交面积

矩形a的左下角的x坐标等于x1,x2中的最小值,y坐标等于y1,y2中的最小值,右上角的x坐标等于x1,x2中的最大值,y坐标等于y1,y2中的最大值
矩形b同上
现在计算相交矩形c的顶点
假设两个矩形相交
矩形c的左下角等于两个矩形中最大左下角
矩形c的右上角等于两个矩形中最小右上角
a1=max(min(x1,x2),min(x3,x4)); //相交矩形的左下角x坐标b1=max(min(...

文章标题:LCP 37. 最小矩形面积
文章链接:https://www.dianjilingqu.com/4314.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>