| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
不就是两次qsort,一直TLE只能呵呵了#include<stdio.h>
#include<stdlib.h>
struct pos
{
int x, y;
};
int cmpx(const void* a, const void* b)
{
if ((*(pos*)a).x != (*(pos*)b).x)
return (*(pos*)a).x - (*(pos*)b).x;
else
return (*(pos*)a).y - (*(pos*)b).y;
}
int cmpy(const void* a, const void* b)
{
if ((*(pos*)a).y != (*(pos*)b).y)
return (*(pos*)a).y - (*(pos*)b).y;
else
return (*(pos*)a).x - (*(pos*)b).x;
}
int main()
{
int t, m, n, k, i, j, cnt;
pos* stone=new pos[150000];
scanf_s("%d", &t);
for (i = 0; i < t; i++)
{
cnt = 0;
scanf_s("%d %d %d", &m, &n, &k);
for (j = 0; j < k; j++)
scanf_s("%d %d", &(stone[j].x), &(stone[j].y));
for (j = 0; j < n; j++)
{
stone[k + j].x = 0;
stone[k + j].y = j + 1;
stone[k + n + j].x = m + 1;
stone[k + n + j].y = j + 1;
}
for (j = 0; j < m; j++)
{
stone[k + 2 * n + j].x = j + 1;
stone[k + 2 * n + j].y = 0;
stone[k + 2 * n + m + j].x = j + 1;
stone[k + 2 * n + m + j].y = n + 1;
}
qsort(stone, k + 2 * n + 2 * m, sizeof(pos), cmpx);
for (j = 0; j < k + 2 * n + 2 * m - 1; j++)
if (stone[j].x == stone[j + 1].x&&stone[j + 1].y - stone[j].y > 2)
cnt++;
qsort(stone, k + 2 * n + 2 * m, sizeof(pos), cmpy);
for (j = 0; j < k + 2 * n + 2 * m - 1; j++)
if (stone[j].y == stone[j + 1].y&&stone[j + 1].x - stone[j].x > 2)
cnt++;
printf_s("%d\n", cnt);
}
delete stone;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator