26 lantimilan NA 947.00 54 13
After solve meeting point, I got one step up in the rank. However, meeting point is not actually very interesting and I should have AC long before. L1 distance is easy because x and y dimension are independent. Linf is a bit different, it seems. Linf is also called Chebyshev distance. Wiki told you that Linf can be converted into L1 by rotating the (x,y) coordinates by 45deg. So you are solving L1 distance instead and that is easy. I got a WA because of integer overflow.
Meeting Point C++
Submission Accepted
13/13 testcases passed
50 Point(s)
View Submission Processed 2012-01-21 23:33 UTC
Meeting Point C++
Wrong Answer
4/13 testcases passed
8 Point(s) View Submission Processed 2012-01-21 23:22 UTC
Subscribe to:
Post Comments (Atom)
firegun17@gmail.com 我特别想问 kingdom connectivity 如何解？？ 我首先用了tarjan 然后缩点， 然后topo 算路径总数， 但是我感觉我算路径总数的时候好像出错了。。只pass了4个。。 能否发给我代码学习一下么？？
ReplyDeletecan u tell me whats wrong with my code??
ReplyDelete/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include
#include
using namespace std;
void exchange(long *a, long *b)
{
long temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(long arr[], long si, long ei)
{
long x = arr[ei];
long i = (si - 1);
long j;
for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}
void quickSort(long arr[], long si, long ei)
{
long pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
int main()
{
long arrx[100000] = {0L};
long arry[100000] = {0L};
long arrX[100000] = {0L};
long arrY[100000] = {0L};
long sum[100000] = {0L};
long arrxy[10000][10000];
double centrX = 0;
double centrY = 0;
long N,min=0L;
cin >> N;
long result = 0;
for(long k=0;k>arrx[k];
cin>>arry[k];
long temp = arrx[k] + arry[k];
arrX[k] = arry[k] - arrx[k];
arrY[k] = temp;
}
quickSort(arrX,0,N-1);
quickSort(arrY,0,N-1);
centrX = N%2 == 0 ? (arrX[N/2 -1] + arrX[N/2])/2 : arrX[N/2 -1];
centrY = N%2 == 0 ? (arrY[N/2 -1] + arrY[N/2])/2 : arrY[N/2 -1];
//cout<<centrX<<endl<<centrY<<endl;
double temp1 = ceil((centrY - centrX)/2);
centrY = ceil((centrX+centrY)/2);
centrX = temp1;
// cout<<centrX<<endl<<centrY<<endl;
double temp = max(fabs(arrx[0] - centrX), fabs(arry[0]-centrY));
int tmpCur = 0;
for(int i=1;i<N;i++){
if(max(fabs(arrx[i]-centrX),fabs(arry[i]-centrY))< temp){
temp = max(fabs(arrx[i]-centrX),fabs(arry[i]-centrY));
tmpCur = i;
}
}
for(int i=0;i<N;i++){
if(i!=tmpCur)
result += max(abs(arrx[i]-arrx[tmpCur]),abs(arry[i]-arry[tmpCur]));
}
cout<<result;
}
HI,
ReplyDeleteI was trying to solve the "meeting point" problem, but only 3 of the test cases are passing..
When i came across ur blog it looked as if the logic behind the code that I have written is same as explained by you..
Am i doing something wrong?
Any kind of help would be really helpful..
Code
-----------
#include
#include
#include
using namespace std;
int main()
{
long int N;
vector xc, yc;
cin >> N;
long long int x,y;
unsigned long long s=0;
while(N--)
{
cin >> x >> y;
xc.push_back(x-y);
yc.push_back(x+y);
}
sort(xc.begin(), xc.end());
sort(yc.begin(), yc.end());
vector::iterator itl = xc.begin();
vector::iterator itr = xc.end();
--itr;
while(itl < itr)
{
s+= (unsigned long long)(*itr - *itl);
++itl;
--itr;
}
itl = yc.begin();
itr = yc.end();
--itr;
while(itl < itr)
{
s+= (unsigned long long)(*itr - *itl);
++itl;
--itr;
}
cout << s/2;
return 0;
}