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 |
又是一道水题,怎么这么点人AC#include <iostream> #include <stdio.h> using namespace std; int main() { int nP; scanf("%d", &nP); int xP[26], zP[26]; for(int i = 0; i < nP; i++){ int num; scanf("%d", &num); for(int j = 0; j < num; j++){ scanf("%d%d", &xP[i], &zP[i]); } } int nL; scanf("%d", &nL); int A[26], B[26], C[26]; for(int i = 0; i < nL; i++){ int x1, z1, x2, z2; scanf("%d%d%d%d", &x1, &z1, &x2, &z2); A[i] = z1-z2, B[i] = x2-x1, C[i] = x1*z2-z1*x2; if(B[i] < 0){ A[i] = -A[i], B[i] = -B[i], C[i] = -C[i]; } } int order[26]; bool isDiv[27] = {0}; isDiv[0] = 1, isDiv[nP] = 1; for(int i = 0; i < nP; i++) order[i] = i; for(int i = 0; i < nL; i++){ int pnc = 0; while(pnc < nP){ int next; for(int j = pnc+1; ; j++){ if(isDiv[j]) { next = j; break; } } if(next == pnc+1){ //区间长度为1,不用再分 pnc = next; continue; } int xianNo = 0; int tempHou[26]; int houNo = 0; for(int j = 0; j < next-pnc; j++){ if(A[i] * xP[order[pnc+j]] + B[i] * zP[order[pnc+j]]+ C[i] > 0){ order[pnc+xianNo] = order[pnc+j]; xianNo ++; } else{ tempHou[houNo] = order[pnc+j]; houNo ++; } } isDiv[pnc+xianNo] = 1; for(int j = 0; j < houNo; j++){ order[pnc+xianNo+j] = tempHou[j]; } pnc = next; } } for(int i = 0; i < nP; i++){ printf("%c", order[i]+'A'); } printf("\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator