2017-2018 ACM-ICPC Southeast USA Regional Contest
前言
只有两道题
剩下的题目得等到猴年马月才能A掉了 T^T
- 计算几何 —— 求两圆交点
https://www.cnblogs.com/AOQNRMGYXLMV/p/5098304.html
Move Away - Gym - 101617F
题意
求多个圆相交区域中的点到原点距离最大值
思路 —— 计算几何
多画几个图就会发现，该点只可能是在圆之间的交点或者原点到圆心的直线与圆的交点
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
const int N = 50;
typedef pair<double, double> pdd;
const double PI = acos(-1);
const double eps = 1e-6;
double x[N], y[N], r[N];
set<pdd> st;
inline double sqr(double x){ return x*x; }
int main(){
int n;
while(~scanf("%d", &n)){
st.clear();
for(int i = 0; i < n; i++){
scanf("%lf%lf%lf", &x[i], &y[i], &r[i]);
for(int j = 0; j < i; j++){
double t1 = 2*r[i] * (x[i] - x[j]);
double t2 = 2*r[i] * (y[i] - y[j]);
double t3 = sqr(r[j]) - sqr(r[i]) - sqr(x[i] - x[j]) - sqr(y[i] - y[j]);
double a = sqr(t1) + sqr(t2);
double b = -2*t1*t3;
double c = sqr(t3) - sqr(t2);
double cs[2] = {(-b + sqrt(b*b - 4*a*c))/(2*a), (-b - sqrt(b*b - 4*a*c))/(2*a)};
double sn[2] = {sqrt(1 - sqr(cs[0])), sqrt(1 - sqr(cs[1]))};
for(int k = 0; k < 2; k++){
double tx = x[i] + r[i] * cs[k];
double ty = y[i] + r[i] * sn[k];
if(fabs(sqr(tx - x[j]) + sqr(ty - y[j]) - sqr(r[j])) > eps) ty = y[i] - r[i] * sn[k];
st.insert(make_pair(tx, ty));
}
}
double ang = atan2(y[i], x[i]);
st.insert(make_pair(x[i] + r[i]*cos(ang), y[i] + r[i]*sin(ang)));
st.insert(make_pair(x[i] + r[i]*cos(ang + PI), y[i] + r[i]*sin(ang + PI)));
}
double ans = 0;
for(set<pdd>::iterator it = st.begin(); it != st.end(); it++){
bool ok = true;
double tx = it->first, ty = it->second;
for(int i = 0; i < n; i++){
if(sqr(tx - x[i]) + sqr(ty - y[i]) > sqr(r[i]) + eps){
ok = false;
break;
}
}
if(ok){
ans = max(ans, sqrt(sqr(tx) + sqr(ty)));
}
}
printf("%.3f\n", ans);
}
}
Long Long Strings - Gym - 101617E
题意
给定两个字符串编辑程序，判断两程序是否相同
思路 —— 冒泡排序
这道题真的可以用“绝妙”来形容！蒟蒻大概也只能理解七成 QAQ
首先我们需要正则化（NormalLize）两个程序，到一个怎样的顺序是最好的呢，删除在先且从后往前删，插入在后且从前往后插
理由如下：
- 删除在前，插入在后，则插入的字符坐标能固定，如果先插入再删除，插入的字符坐标可能有些往前挪，有些不变
- 删除从后往前删，则后面删除的坐标不会有影响，如果从前往后删，那么后续删除的坐标实际上会不断地往后挪
- 插入从前往后插，则后面插入的坐标不会有影响，如果从后往前插，那么后续的插入实际上会把已经插入的字符往后挪
那么用冒泡排序的思想，动态维护坐标间的关系，就可以将程序正则化，最后比较即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct Operation{
char op;
ll idx;
char ch;
};
vector<Operation> vec1, vec2;
inline void init(){
vec1.clear();
vec2.clear();
}
void readVec(vector<Operation>& vec){
char op[2], ch[2] = {};
ll idx;
while(scanf("%s", op) && op[0] != 'E'){
scanf("%lld", &idx);
if(op[0] == 'I') scanf("%s", ch);
vec.emplace_back(Operation{op[0], idx, ch[0]});
}
}
void normalizeVec(vector<Operation>& vec){
for(int i = 1; i < (int)vec.size(); i++){
for(int j = i; j > 0; j--){
if(vec[j - 1].op == 'D' && vec[j].op == 'D' && vec[j - 1].idx <= vec[j].idx){
swap(vec[j - 1], vec[j]);
vec[j - 1].idx++;
}else if(vec[j - 1].op == 'I' && vec[j].op == 'I' && vec[j - 1].idx >= vec[j].idx){
swap(vec[j - 1], vec[j]);
vec[j].idx++;
}else if(vec[j - 1].op == 'I' && vec[j].op == 'D'){
if(vec[j - 1].idx == vec[j].idx){
vec.erase(vec.begin() + j - 1, vec.begin() + j + 1);
i -= 2;
break;
}else if(vec[j - 1].idx > vec[j].idx){
swap(vec[j - 1], vec[j]);
vec[j].idx--;
}else{
swap(vec[j - 1], vec[j]);
vec[j - 1].idx--;
}
}else{
break;
}
}
}
}
bool compVec(){
if(vec1.size() != vec2.size()) return false;
for(int i = 0; i < (int)vec1.size(); i++){
if(vec1[i].op != vec2[i].op || vec1[i].idx != vec2[i].idx) return false;
if(vec1[i].op == 'I' && vec1[i].ch != vec2[i].ch) return false;
}
return true;
}
int main(){
init();
readVec(vec1);
readVec(vec2);
normalizeVec(vec1);
normalizeVec(vec2);
puts(compVec() ? "0" : "1");
}
