本文主要是介绍2024东北四省赛——M House,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
cf上有题解,我写这个只想说真服了,卡double了导致一直没做出来
开long double过的
贴一下我的代码
#include <bits/stdc++.h>using namespace std;
typedef long double LD;
typedef long long LL;
#define int LL
#define double LD
const int N = 5007, M = 50007, INF = 0x3f3f3f3f;
const double DINF = 1e18, eps = 1e-10;
const double PI = acosl(-1.0l);struct Point {//二维点double x, y;Point(double x = 0, double y = 0) : x(x), y(y) {}//构造函数
};typedef Point Vector;//向量 + 向量 = 向量,点 + 向量 = 向量
Vector operator+(Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }//点 - 点 = 向量(向量BC = C - B)
Vector operator-(Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }//向量 * 数 = 向量
Vector operator*(Vector A, double p) { return Vector(A.x * p, A.y * p); }//向量 / 数= 向量
Vector operator/(Vector A, double p) { return Vector(A.x / p, A.y / p); }//点/向量的比较函数
bool operator<(const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }struct Line {//直线定义Vector v;Point p;Line() {}Line(Vector v, Point p) : v(v), p(p) {}Point get_point_in_line(double t) {//返回直线上一点P = p + v * treturn p + v * t;}
};//判断相等
int sgn(double x) {//也是dcmpif (fabsl(x) < eps)return 0;if (x < 0)return -1;return 1;
}//重载等于运算符
bool operator==(const Point& a, const Point& b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }//点积(满足交换律)
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }//向量的叉积(不满足交换律)
double Cross(Vector A, Vector B) { return A.x * B.y - B.x * A.y; }//计算两点距离距离
double dis(Vector a, Vector b) {return sqrtl((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y));
}//取模(模长,求长度)
double Length(Vector A) { return sqrtl(Dot(A, A)); }int Relation(Point A, Point B, Point C) {// 1 left -1 right 0 inint c = sgn(Cross((B - A), (C - A)));if (c < 0) return 1;else if (c > 0) return -1;return 0;
}inline Point FootPoint(Point p, Point a, Point b) {Vector x = p - a, y = p - b, z = b - a;double len1 = Dot(x, z) / Length(z), len2 = -1.0 * Dot(y, z) / Length(z);//分别计算AP,BP在AB,BA上的投影return a + z * (len1 / (len1 + len2));//点A加上向量AF
}int n;
Point p[N];
map<pair<double, double>, int> mp;
int ans = 0;signed main() {scanf("%lld", &n);for (int i = 1; i <= n; i++) {scanf("%Lf %Lf", &p[i].x, &p[i].y);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {mp.clear();if (i == j) continue;int l = 0, r = 0;//Line L = Line(p[i] - p[j], p[i]);for (int k = 1; k <= n; k++) {if (k == i || k == j) continue;int t = Relation(p[i], p[j], p[k]);if (t == 0) continue;else if (t == 1) {double t1, t2;t1 = dis(p[i], p[k]);t2 = dis(p[j], p[k]);
// cout<<t1<<" "<<t2<<endl;if (t1 == t2) {l++;}}else {if (Dot(p[i] - p[j], p[k] - p[i]) == 0 || Dot(p[i] - p[j], p[k] - p[j]) == 0) {double t1, t2;t1 = dis(p[i], p[k]);t2 = dis(p[j], p[k]);if (mp.count({ t2, t1 })) {mp[{t2, t1}] = 0;r++;}else { mp[{t1, t2}] = 1; }}}}
// cout<<l<<" "<<r<<" "<<i<<" "<<j<<endl;ans += l * r;}}printf("%lld\n", ans);return 0;
}
这篇关于2024东北四省赛——M House的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!