尝试了好多例子,结果都是正确的为什么pta一直给我答案错误。
#include
#include
#include
using namespace std;
struct point{
double x,y;
};
double Closet(point s[], int low, int high);
double Distance(point a, point b);
void QuickSort(point r[], int first, int end);
int Partition(point r[], int first, int end);
void Merge(point r[], point r1[], int s, int m, int t);
void MergeSort(point r[], int s, int t);
void record(point p1, point p2);
double a1,b1,a2,b2;
int main() {
double miniDist;
int n;
cin>>n;
point s[10000];
for (int i = 0; i < n; ++i) {
cin>>s[i].x>>s[i].y;
}
MergeSort(s, 0, n-1);
miniDist = Closet(s, 0, n-1);
if(a1+b1 <= a2+b2) {
cout<<"("<<setprecision(2)<<fixed<<a1<<","<<b1<<"),("<<a2<<","<<b2<<"),";
cout<<"miniDist="<<setprecision(3)<<fixed<<miniDist;
}else{
cout<<"("<<setprecision(2)<<fixed<<a2<<","<<b2<<"),("<<a1<<","<<b1<<"),";
cout<<"miniDist="<<setprecision(3)<<fixed<<miniDist;
}
return 0;
}
double Closet(point s[], int low, int high){
double d1, d2, d3, d;
int mid, i, j, index;
point p[high+1];
if (high - low == 1){
record(s[low], s[high]);
return Distance(s[low], s[high]);
}
if (high - low == 2){
d1 = Distance(s[low],s[low+1]);
d2 = Distance(s[low+1], s[high]);
d3 = Distance(s[low], s[high]);
if ((d1<d2) && (d1<d3)){
record(s[low], s[low+1]);
return d1;
}else if (d2 < d3){
record(s[low+1], s[high]);
return d2;
}else{
record(s[low], s[high]);
return d3;
}
}
mid = (low + high) / 2;
d1 = Closet(s, low, mid);
double x1 = a1, x2 = a2, y1 = b1, y2 = b2;
d2 = Closet(s, mid + 1, high);
double m1 = a1, m2 = a2, n1 = b1, n2 = b2;
if (d1 <= d2){
d = d1;
a1 = x1;
a2 = x2;
b1 = y1;
b2 = y2;
}else{
d = d2;
a1 = m1;
a2 = m2;
b1 = n1;
b2 = n2;
}
index = 0;
for (i = mid; (i >= low) && ((s[mid].x - s[i].x) < d); i--) {
p[index++] = s[i];
}
for (i = mid + 1; (i <= high) && ((s[i].x - s[mid].x) < d); i++) {
p[index++] = s[i];
}
QuickSort(p, 0, index-1);
for (i = 0; i < index; i++) {
for (j = i+1; j < index; j++) {
if (p[j].y - p[i].y >= d) {
break;
}else{
d3 = Distance(p[i], p[j]);
if(d3 < d) {
d = d3;
record(p[i], p[j]);
}
}
}
}
return d;
}
double Distance(point a, point b){
return sqrt((a.x - b.x)(a.x - b.x) + (a.y - b.y)(a.y - b.y));
}
void record(point p1, point p2) {
a1 = p1.x;
b1 = p1.y;
a2 = p2.x;
b2 = p2.y;
}
void QuickSort(point r[], int first, int end){
int pivot;
if (first < end){
pivot = Partition(r, first, end);
QuickSort(r, first, pivot-1);
QuickSort(r, pivot+1, end);
}
}
int Partition(point r[], int first, int end){
int i = first, j = end;
while (i < j) {
while (i < j && r[i].y <= r[j].y) j--;
if (i < j) {
point temp = r[j];
r[j] = r[i];
r[i] = temp;
i++;
}
while (i < j && r[i].y <= r[j].y) i++;
if (i < j) {
point temp = r[j];
r[j] = r[i];
r[i] = temp;
j--;
}
}
return i;
}
void Merge(point r[], point r1[], int s, int m, int t){
int i = s, j = m+1, k = s;
while(i <= m && j <= t){
if (r[i].x <= r[j].x)
r1[k++] = r[i++];
else
r1[k++] = r[j++];
}
while(i <= m)
r1[k++] = r[i++];
while(j <= t)
r1[k++] = r[j++];
}
void MergeSort(point r[], int s, int t){
int m;
point r1[10000];
if(s == t) return;
else{
m = (s+t)/2;
MergeSort(r, s, m);
MergeSort(r, m+1, t);
Merge(r, r1, s, m, t);
for (int i = s; i <= t; ++i) {
r[i] = r1[i];
}
}
}