文章目录

• • • 十进制转16进制
    • 16进制转十进制
    • 36进制 [0-9, A-Z] ---- 16改为36
    • 3068. 扫描线

十进制转16进制

#include
using namespace std;char change(int x)
{if(x < 10) return x + '0';  //【0-9】 return (char)('A' + x - 10); //【A-F】 
}int main()
{int n;cin >> n;string s = ""; while(n){char x = change(n % 16);n /= 16;s = x + s; //【省reverse】 }cout << s << endl; return 0; 
} 

16进制转十进制

#include
using namespace std;
typedef long long LL;int get(char c)
{if(c - '0' < 9) return  c - '0';return c - 'A' + 10;
}int main() 
{//string读入 hexstring s;cin >> s;res = 0; for(int i = 0; i < s.size(); i++) //秦九韶{res = res * 16 + get(s[i]);}cout << res << endl;return 0; 
} 

36进制 [0-9, A-Z] ---- 16改为36

纯属娱乐：

	//int读入（没有A-F的hex） (娱乐hh)
//	int n;  //用秦九韶 - 从高位开始 - 先翻转n 
//	scanf("%d", &n);
//	string sn = to_string(n);
//	cout << sn << endl;
//	reverse(sn.begin(), sn.end());
//	
//	int ns = stoi(sn);	
//	cout << ns << endl;
//	LL res = 0;
//	while(ns)
//	{
//		res = res * 16 + ns % 10;
//		ns /= 10;
//	}
//	cout << res << endl;

3068. 扫描线

在二维平面中给定 n 个两条边分别与 x 轴和 y 轴平行的矩形，请你求出它们的面积并。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含四个整数 x1,y1,x2,y2，表示其中一个矩形的左下角坐标 (x1,y1) 和右上角坐标 (x2,y2)。
注意，坐标轴 x 轴从左向右延伸，y 轴从下向上延伸。

输出格式
一个整数，表示矩形的面积并。

数据范围
1≤n≤1000,
−109−10^9−109≤x1 −109−10^9−109≤y1

输入样例：
2
10 10 20 20
15 15 25 25

输出样例：
175

二维坐标合并O(n2logn)\large二维坐标合并O(n^2logn)二维坐标合并O(n2logn)

①预处理划分区域坐标-枚举(矩形横坐标l[i].x,r[i].x)放入xs[类似离散化但不去重]sort 
[(xs[i]!=xs[i+1]时)枚举划分区域]
②range_area计算区域面积：先计算与区域有交集的矩形{l[i].y,r[i].y}存到q[cnt]-sort做区间合并:
区域面积=高度和res * 宽度(b-a)   

#include 
#include 
#include 
#include #define x first
#define y secondusing namespace std;typedef long long LL;
typedef pair PII;
const int N = 1010;int n;
PII l[N], r[N]; //左上角 和 右下角
PII q[N]; //存每个区域有交集的矩形高度LL range_area(int a, int b) //每个垂直划分区域(宽度) - 左右坐标
{int cnt = 0;  //预处理 - 矩形 [左,右]>=[a, b] 数量for (int i = 0; i < n; i ++ )if (l[i].x <= a && r[i].x >= b) //矩形左右>=区域左右边界 - 有交集[矩形可被分割]q[cnt ++ ] = {l[i].y, r[i].y}; //存矩形高度if (!cnt) return 0;  //没有矩形有交集sort(q, q + cnt); //【区间合并-高度y】-同一区域有交集的矩形高度y做区间合并LL res = 0;int st = q[0].x, ed = q[0].y; //边界取第一个, for (int i = 1; i < cnt; i ++ )  //从1开始(第二个边界开始)比较if (q[i].x <= ed) ed = max(ed, q[i].y);else{res += ed - st; //[累加高度]  st = q[i].x, ed = q[i].y;}res += ed - st; //[累加高度]return res * (b - a); //累加高 * 宽度
}int main()
{scanf("%d", &n);vector xs; //存所有横坐标xfor (int i = 0; i < n; i ++ ){scanf("%d%d%d%d", &l[i].x, &l[i].y, &r[i].x, &r[i].y);xs.push_back(l[i].x), xs.push_back(r[i].x);  //存所有点的横坐标x     }sort(xs.begin(), xs.end()); //横坐标排序-(枚举区间宽度) - 无需判重LL res = 0; //LLfor (int i = 0; i + 1 < xs.size(); i ++ ) //i+1 < 边界xs.size()if (xs[i] != xs[i + 1]) //枚举宽度 - (重复坐标就不判断)res += range_area(xs[i], xs[i + 1]); //加上面积printf("%lld\n", res);return 0;
}

扫描线原理图-划分：

区间合并版

LL range_area(int a, int b)
{int cnt = 0;for(int i = 0; i < n; i++){if(l[i].x <= a && r[i].x >= b) q[cnt ++] = {l[i].y, r[i].y};}if(cnt == 0) return 0;sort(q, q + cnt);LL res = 0;int st = -2e9, ed = -2e9; //边界for(int i = 0; i < cnt; i++)   {if(ed < q[i].x) {if(st != -2e9)res += ed - st; //非边界(特判第一个)st = q[i].x, ed = q[i].y;}else ed = max(ed, q[i].y);}if(st != -2e9)res += ed - st;  //别忘加最后一个(若没有合并区间,则cnt已经return,可不加if判断)return res * (b - a);
}