题目描述
Pb 去郊游啦！他来到一块空地打算在这里搭一个帐篷。但是,帐篷的四个支撑点不能在落在任何位置上,而只能落在一些固定点上。现在,他找到地面上有 N 个点可以支撑帐篷。（四个支撑点必须围成一个矩形） 他想知道依次每加多一个点，搭帐篷的方法数。输入格式第1行：一个整数N第2行至N+1行：每行有两个整数的x, y作为一个点的坐标。输出格式共N行：第i行表示当前加入第i个点后可以搭帐篷的方案数。这题的关键在于如何判断任意四个点是矩形。
在数学上，矩形的判定有4种方式1.有三个角是直角的四边形是矩形；2.对角线互相平分且相等的四边形是矩形；3.有一个角为直角的平行四边形是矩形；4.对角线相等的平行四边形是矩形。于是显然我们可以看出来，第一种和第三种方法肯定时候超时的而第二种和第四种，从本质上讲，我们在是实现时是一样的于是现在的问题是我们要如何快速判断对角线相等且平分
我们可以知道的是合法的对角线一定是这样的，对于一个矩形的两条对角线，我们可以知道他们的交叉点是相等的
而这个交叉点的横坐标是如图确定出一条对角线的两个点横坐标的和的一半，纵坐标同理所以我们要先解决这个点，但是接着，问题出现了，只靠这一个信息是不够的。我们目前有两个选择：1.获取足够多的可以确定是矩形的信息2.将三个点（矩形的两个顶点和对角线的中点）统一成一个值显然我们肯定不愿意写第一种，因为很麻烦所以我们可以利用第二种方式，于是我们很自然的想到了hash，为了保证答案的准确，我们只需要准备一个足够复杂和hash函数即可而每一个hash过的数，我们用挂链法记录下来，若碰到了两个相等或是误差极小hash值，我们可以确定这四个点可以构成一个矩形，答案数加一具体实现见代码1 #include2 #define ll long long 3 using namespace std; 4 const int maxn = 1100; 5 const int mod = 232337; 6 const double cri = 0.0000001; 7 struct enkidu { 8 double x, y; 9 }a[maxn];10 struct Shiki { //Ryougi11 double x, y, z;12 int net;13 }e[mod + 86];14 int n, ans = 0;15 int ha[mod + 86], len = 0;16 17 inline int read() {18 int x = 0, y = 1;19 char ch = getchar();20 while(!isdigit(ch)) {21 if(ch == '-') y = -1;22 ch = getchar();23 }24 while(isdigit(ch)) {25 x = (x << 1) + (x << 3) + ch - '0';26 ch = getchar();27 }28 return x * y;29 }30 31 inline void insert(ll kk, double xx, double yy, double zz) {32 e[++len].x = xx;33 e[len].y = yy;34 e[len].z = zz;35 e[len].net = ha[kk];36 ha[kk] = len;37 } 38 39 inline bool check(double a, double b) {40 if(abs(a - b) < cri) return 1;41 else return 0;42 } 43 44 inline void hash(double x, double y, double z) {45 ll k = x * y + y * z + x * z + x + y + z + mod;46 if(k < 0) k = -k;47 k %= mod;48 //cout << k << '\n';49 for(int i = ha[k]; i; i = e[i].net) 50 if(check(x, e[i].x) && check(y, e[i].y) && check(z, e[i].z)) 51 ans++;52 insert(k, x, y, z);53 }54 55 int main() {56 n = read();57 for(int i = 1; i <= n; ++i) 58 a[i].x = read(), a[i].y = read();59 for(int i = 1; i <= n; ++i) {60 double x, y, z;61 for(int j = 1; j < i; ++j) {62 x = (a[i].x + a[j].x) / 2;63 y = (a[i].y + a[j].y) / 2;64 z = ((a[i].x - a[j].x) * x + (a[i].y - a[j].y) * y) / (a[i].x + a[j].y);65 hash(x, y, z);66 }67 cout << ans << '\n'; 68 }69 return 0;70 }
目前接到反映加实测，上面那份代码好像死了....我....天知道发生了什么....
下面随便摆一份Ac的（hash函数不同
1 #include2 #define ll long long 3 using namespace std; 4 const int maxn = 1100; 5 const int mod = 2323237; 6 struct node { 7 double x, y; 8 }a[maxn]; 9 struct nn {10 double x, y, z;11 ll net;12 }e[mod + 86];13 int n; 14 int lin[mod + 86];15 int tot = 0, ans = 0;16 double x, y, z;17 18 inline bool pd(double a, double b) {19 if(abs(a - b) < 0.000000001) return 1;20 return 0;21 }22 23 inline void insert(double x, double y, double z, ll k) {24 e[++tot].x = x;25 e[tot].y = y;26 e[tot].z = z;27 e[tot].net = lin[k];28 lin[k] = tot;29 }30 31 inline void hash(double x, double y, double z) {32 ll k = x * y + y * z + x * z + x + y + z + mod;33 if(k < 0) k = -k;34 k %= mod;35 // cout << 'k' << ':' << k <<'\n';36 for(int i = lin[k]; i; i = e[i].net) 37 if(pd(e[i].x, x) && pd(e[i].y, y) && pd(e[i].z, z)) 38 ans++;39 insert(x, y, z, k); 40 }41 42 int main() {43 // freopen("tents.in", "r", stdin);44 // freopen("tents.out", "w", stdout);45 cin >> n;46 for(int i = 1; i <= n; i++) {47 cin >> a[i].x >> a[i].y;48 for(int j = 1; j < i; ++j) {49 x = (a[i].x + a[j].x) / 2;50 y = (a[i].y + a[j].y) / 2;51 z = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);52 hash(x, y, z);53 }54 cout << ans << '\n';55 }56 fclose(stdin);57 fclose(stdout);58 return 0;