標籤
- C
- android
- Objective-c
- Sort
- BlueTooth
- Python
- 133
- Apache
- ArrayList
- BluetoothChat
- C sharp
- C#
- CVS
- CheckBox
- Closest Pair
- Console.ReadLine
- HashMap
- NFC
- NSDocumentDirectory
- NSString
- Pandaboard
- SQLite
- UIAlertController
- VB
- Xcode6
- driver
- execSQL
- gatt error
- httpd.conf
- office
- primie check
- property
- sharedApplication
- 小小問題
2010年12月4日 星期六
[C] Closest Pair Problem
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
struct point
{
double x;
double y;
};
struct point p[200000];
double length(struct point, struct point);
int cmp(const void *p1, const void *p2);
int main()
{
FILE *fin;
char * pEnd;
char x[200000];
int count;
int i,j;
int t;
double d;
double mind;
int mi=0,mj=0; //記錄最短距離兩點座標用
char key; //switch case用
printf("(1)10k point \n");
printf("(2)50k point \n");
printf("(3)200k point \n");
printf("(4)test \n");
printf("select file : ");
scanf("%c",&key);
switch(key)
{
case '1': fin = fopen("p10k.txt","r");
count=10000;
break;
case '2': fin = fopen("p50k.txt","r");
count=50000;
break;
case '3': fin = fopen("p200k.txt","r");
count=200000;
break;
case '4': fin = fopen("test.txt","r");
count=10;
break;
default:
return 0;
}
if(fin == NULL)
{
printf("Fail To Open File !!");
return;
}
for(i=0 ; i<count ; i++)
{
if(fgets(x, 1000 , fin) != NULL)
{
p[i].x = strtod(x,&pEnd); //strtod=將字串轉換為雙精度數值
p[i].y = strtod(pEnd,NULL);
}
}
qsort(p,count,sizeof(struct point),cmp);
printf("sorting...\n");
mind = ( (p[0].x - p[1].x)*(p[0].x - p[1].x) + (p[0].y - p[1].y)* (p[0].y - p[1].y) );
printf("loading...\n");
for(i=0; i<count ; i++)
{
for(j=i+1 ; j<count ; j++)
{
if( (p[i].x - p[j].x)*(p[i].x - p[j].x) < mind ) //p[i].x到p[j].x距離平方 若小於mind
{
if( (p[i].y - p[j].y)*(p[i].y - p[j].y) < mind )
{
d=( (p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)* (p[i].y - p[j].y) );
if(d<mind)
{
mi=i;
mj=j;
mind=d;
}
else
continue;
}
else
continue;
}
else //此break是因為, 當p[i].x到p[j].x距離已經超過mind了, 所以後面的點可以不用看
break;
}
}
mind=sqrt(mind); //sprt=計算平方根值
printf("mini L: %.2f\n", mind);
printf("point:(%.0f , %.0f)\n", p[mi].x, p[mi].y); //p1
printf(" to\n");
printf("point:(%.0f , %.0f)\n", p[mj].x, p[mj].y); //p2
system("pause");
fclose(fin);
}
int cmp(const void *p1, const void *p2) //qsort 自訂cmp副程式
{
return (*(struct point *)p1).x > (*(struct point *)p2).x ? 1 : -1;
}
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言