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