#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
bool cmp(P a, P b) {
if(a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
int main () {
vector<P> v;
ll n, x, y;
cin >> n >> x >> y;
for(int i = 0; i < n; ++i) {
ll a, b;
cin >> a >> b;
ll dis = (x - a) * (x - a) + (y - b) * (y - b);
v.push_back(P(dis, i + 1));
}
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < 3; ++i) {
cout << v[i].second << endl;
}
}
#include <bits/stdc++.h>
using namespace std;
int main () {
int jingguo = 0;
int douliu = 0;
int n, k, t, xl, yd, xr, yu;
cin >> n >> k >> t >> xl >> yd >> xr >> yu;
while(n--) {
int x, y;
bool isjingguo = 0;
int temp = 0;
int maxx = -1;
for(int i = 0; i < t; ++i) {
cin >> x >> y;
if(x >= xl && x <= xr && y >= yd && y <= yu) {
isjingguo = 1;
temp++;
}
else {
temp = 0;
}
maxx = max(temp, maxx);
}
if(maxx >= k) {
douliu++;
}
if(isjingguo) {
jingguo++;
}
}
cout << jingguo << endl;
cout << douliu << endl;
}
记忆化DFS+拓扑排序判环
#include <bits/stdc++.h>
using namespace std;
typedef struct
{
std::vector<string> op_item;
string op;
int in;
int out;
}Yuanjian;
typedef struct
{
int op_num;
std::vector<int> input;
std::vector<int> output;
}Guapi;
typedef struct
{
std::vector<int> mubiao;
}Topoint;
Topoint topoint[505];
Yuanjian nb[505];
int save[505];
std::vector<int> input;
int getNum(string op_item) {
int num = 0;
int quan = 1;
for(int i = op_item.size() - 1; i > 0; --i) {
num += (op_item[i] - '0') * quan;
quan *= 10;
}
return num;
}
bool getAns(Yuanjian temp) {
string op = temp.op;
if(op == "NOT") {
bool op_num;
if(temp.op_item[0][0] == 'O') {
if(save[getNum(temp.op_item[0])] == -1) {
save[getNum(temp.op_item[0])] = getAns(nb[getNum(temp.op_item[0])]);
}
op_num = save[getNum(temp.op_item[0])] ;
} else {
op_num = input[getNum(temp.op_item[0])];
}
return !op_num;
}
vector<bool> op_num(temp.op_item.size());
for(int i = 0; i < int(op_num.size()); ++i) {
if(temp.op_item[i][0] == 'O') {
if(save[getNum(temp.op_item[i])] == -1) {
save[getNum(temp.op_item[i])] = getAns(nb[getNum(temp.op_item[i])]);
}
op_num[i] = save[getNum(temp.op_item[i])];
} else {
op_num[i] = input[getNum(temp.op_item[i])];
}
}
if(op == "AND") {
bool ans = op_num[0];
for(int i = 1; i < int(op_num.size()); ++i) {
ans &= op_num[i];
}
return ans;
}
if(op == "OR") {
bool ans = op_num[0];
for(int i = 1; i < int(op_num.size()); ++i) {
ans |= op_num[i];
}
return ans;
}
if(op == "XOR") {
bool ans = op_num[0];
for(int i = 1; i < int(op_num.size()); ++i) {
ans ^= op_num[i];
}
return ans;
}
if(op == "NAND") {
bool ans = op_num[0];
for(int i = 1; i < int(op_num.size()); ++i) {
ans &= op_num[i];
}
return !ans;
}
if(op == "NOR") {
bool ans = op_num[0];
for(int i = 1; i < int(op_num.size()); ++i) {
ans |= op_num[i];
}
return !ans;
}
return 0;
}
bool topSort(int N) {
queue<int> q;
for(int i = 1; i <= N; ++i) {
if(nb[i].in == 0) {
q.push(i);
}
}
std::vector<int> ans;
while(!q.empty()) {
int p = q.front();
q.pop();
ans.push_back(p);
for(int i = 0; i < topoint[p].mubiao.size(); ++i) {
int temp = topoint[p].mubiao[i];
nb[temp].in--;
if(nb[temp].in == 0) {
q.push(temp);
}
}
}
if(ans.size() != N) {
return 1;
} else {
return 0;
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int Q;
cin >> Q;
while(Q--) {
// Final final[10005];
int M, N;
cin >> M >> N;
for(int i = 1; i <= N; ++i) {
topoint[i].mubiao.clear();
nb[i].in = 0;
nb[i].out = 0;
}
bool isOK = 0;
for(int i = 1; i <= N; ++i) {
cin >> nb[i].op;
int num;
cin >> num;
nb[i].op_item.resize(num);
for(int j = 0; j < num; ++j) {
int first_num = i;
cin >> nb[i].op_item[j];
int second_num = getNum(nb[i].op_item[j]);
if(nb[i].op_item[j][0] == 'O' && first_num == second_num) {
isOK = 1;
continue;
}
if(nb[i].op_item[j][0] == 'O') {
nb[first_num].in++;
nb[second_num].out++;
topoint[second_num].mubiao.push_back(first_num);
}
}
}
if(!isOK && topSort(N)) {
isOK = 1;
}
int S;
cin >> S;
std::vector<Guapi> guapi;
guapi.resize(S);
for(int i = 0; i < S; ++i) {
guapi[i].input.resize(M + 1);
for(int j = 1; j <= M; ++j) {
cin >> guapi[i].input[j];
}
}
for(int i = 0; i < S; ++i) {
cin >> guapi[i].op_num;
for(int j = 0; j < guapi[i].op_num; ++j) {
int temp;
cin >> temp;
guapi[i].output.push_back(temp);
}
}
if(isOK) {
cout << "LOOP" << endl;
continue;
}
for(int i = 0; i < S; ++i) {
std::vector<bool> ans;
input = guapi[i].input;
memset(save, -1, sizeof save);
for(int j = 0; j < guapi[i].output.size(); ++j) {
if(save[guapi[i].output[j]] == -1) {
save[guapi[i].output[j]] = getAns(nb[guapi[i].output[j]]);
}
cout << save[guapi[i].output[j]] << " ";
}
cout << endl;
}
}
return 0;
}
根据a和b+c的关系分成两种情况，剩下情况都是两个线段加上一段圆弧
两个线段：由勾股定理求解。
一段圆弧：先由余弦定理求出两点与到圆心直线夹角，然后由几何关系做差得到圆弧对应圆心角，乘以半径后得到弧长。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double getDis(std::vector<ll> p1, std::vector<ll> p2) {
ll ans = 0ll;
for(int i = 0; i < p1.size(); ++i) {
ans += (p1[i] - p2[i]) * (p1[i] - p2[i]);
}
return sqrt(ans);
}
int main () {
double yuchuliDian[2002];
double ans[2002];
memset(ans, 0.0, sizeof ans);
memset(yuchuliDian, 0.0, sizeof yuchuliDian);
int n, m;
scanf("%d%d", &n, &m);
ll r;
scanf("%lld", &r);
std::vector<std::vector<ll> > point(m, std::vector<ll> (n));
std::vector<ll> xin;
for(int i = 0; i < n; ++i) {
ll temp;
scanf("%lld", &temp);
xin.push_back(temp);
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
scanf("%lld", &point[i][j]);
}
}
for(int i = 0; i < m; ++i) {
for(int j = i + 1; j < m; ++j) {
if(yuchuliDian[i] == 0.0) {
yuchuliDian[i] = getDis(point[i], xin);
}
if(yuchuliDian[j] == 0.0) {
yuchuliDian[j] = getDis(point[j], xin);
}
double io = yuchuliDian[i];
double jo = yuchuliDian[j];
double ij = getDis(point[i], point[j]);
double jiaoi = acos(double(r) / io);
double jiaoj = acos(double(r) / jo);
double jiaoioj = acos((io * io + jo * jo - ij * ij) / (2.0 * io * jo));
if(jiaoioj > jiaoi + jiaoj) {
double jiao = jiaoioj - jiaoi - jiaoj;
ans[i] += jiao * double(r) + sqrt(io * io - double(r * r)) + sqrt(jo * jo - double(r * r));
ans[j] += jiao * double(r) + sqrt(io * io - double(r * r)) + sqrt(jo * jo - double(r * r));
} else {
ans[i] += ij;
ans[j] += ij;
}
}
}
for(int i = 0; i < m; ++i) {
printf("%.14lf
", ans[i]);
}
return 0;
}