a245. 王老師愛兩條線
內容 ：
最近，柏油高中的數學老師們忽然愛上了兩條線，於是柏油高中的學生們就倒楣了......他們的作業全部都是滿滿的兩條線，不管是題目還是答案，就連廁所每個磁磚的兩側，每個學生的頭上，都是滿滿的兩條線。
這真的是太愚蠢了......。
於是在虹原大學上課的你，你的筆電「嘟」的一聲，學弟傳訊息過來了：
「學長救命呀！」
「什麼狗啊......」你不知不覺說了這句，就把筆電闔上。
就在下一秒，你的手機響了，被全班盯著看。
「呃......」你嬌羞地淚奔出教室接電話。
「你ㄎㄧ笑了嗎= =，居然在上課時間打電話給我！」接起手機，你馬上開始大吼。
「對不起麻學長......快點救救我，我們學校裡面某個王老師才真的ㄎㄧ笑，自從你離開這座學校之後，他看到了神作三條線，他就忽然發瘋，在學校傳教兩條線的好處，現在整個學校都在『兩條線收束協會』的統治之下，......」學弟的故事還沒說完，你已經露出不耐煩的神色，打斷學弟的發言。
「講重點好嗎？！我剛剛衝出來接電話的事情已經被教授知道了，要是講太久的話又會被那位男教授約出去喝咖啡的啦。」
「唉呦不要這樣麻，我知道學長人正，心地又好，一定會幫我的說。那我繼續講下去：因為在『兩條線收束協會』的影響之下，我們期中考的題目全部都變成了兩條線......」
「那還不簡單，直接把負號去掉就好了呀。」再次打斷學弟發言。
「NOOOOOOO不對呀！！事情不是憨人所想的那麼簡單，因為題目都變成了兩條線，使得這座學校的學生思想退化回18世紀，而我和其他幾個人是少數和『協會』抗爭的人，因此才沒有被洗腦，但是要改變『協會』統治的現實，我們必須要找回消失的第三條線......」
「喔？是嗎？那你就去其他地方找呀。」你交談的同時，隨手將自己另外一支手機拿出來，順手按了三個數字。
「不，我已經找到了......那就是......」當然，正常人能聽到這裡就已經很厲害了，你早就很想掛掉了。
正當轉身回去上課時，你的視線變得模糊，整個空間開始在旋轉。你四肢開始扭曲，身體往一邊傾倒，最後做倒在地面上，表情顯露出極大的不舒服。
一段時間後，周圍的視線開始漸漸清晰，空間也漸漸正常，此時你發現自己倒在柏油高中的大馬路上，穿著以前的制服。
「這是什麼狗呀......」你咕噥了一聲，看起來一副在九彎十八拐走九遍的模樣，身體平衡還無法恢復正常。
此時，剛剛學弟打電話過來的手機響了，是簡訊。
發信人：F8
簡訊內容如下：
『
嘿嘿嘿......你已經被『協會』給盯上了，
如果你沒有回答出接下來的問題，那麼...
...嘿嘿嘿......
』
「這又是啥狗......」怪了，今天奇怪的事實在太多了。這時又傳來另外一封簡訊，發信者依然是F8。
『
給你三個點(0, 0), (1, 1), (2, 2)，請找出某
點P，使得點P跟其他三個點的距離和為最
小。若有答案請回覆。
』
「啥狗......」你已經說了四遍，很順手地就把 2 * sqrt(2) 傳了過去。
此時，強風把你的鞋帶吹掉了，正當你低頭綁鞋帶時，說時遲那時快，「啪」的一聲，你看見自己面前不遠處有一道彈痕，從燒焦的痕跡以及冒煙狀況來看，是剛剛形成的。
是剛剛形成的。
是剛剛形成的。
是剛剛形成的！
「什麼鬼呀......」你終於換了另外一句台詞，這時又來了另外一封簡訊：
『
You!!!
Can not PASS!!!!!!!
同學，乖乖繼續念你的高五吧=ˇ=
愛你的王老師
』
「什麼！！！NOOOOOOOOOOOOOOOOOOOOOOO~~~~~~老師不要當我呀！！！！」上大學之後，你對於「Pass」這個字眼變得非常敏感，所以崩潰了。
其他人幫他看看，到底是為什麼算錯了呢？
輸入說明
：
輸入有多筆測資，一開始會有單獨一行的數 T <= 10000，代表測試組數。
接著每筆測試資料中，第一行僅有一整數 N <= 1000，代表輸入點數。接著 N 行，每行有兩個整數 -10000 <= X, Y <= 10000，代表點的座標。
輸出說明
：
範例輸入 ：
1 3 0 0 1 1 2 2
範例輸出 ：
4 1
提示
：
出處
：
作法 : DP
這題不一定要 DP，用中位數也可以寫
因為 X 跟 Y 軸無關，因此分開做，找到一個 X 座標到所有點的 X 座標和最小，
把兩次算的個數加總跟相乘就是答案了。
/**********************************************************************************/
/* Problem: a245 "王老師愛兩條線" from 板橋高中練習題 */
/* Language: C (1528 Bytes) */
/* Result: AC(2.2s, 412KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-15 23:32:40 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
int main() {
int t, n, X[1001], Y[1001], i;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int sumx = 0, sumy = 0;
for(i = 0; i < n; i++) {
scanf("%d %d", &X[i], &Y[i]);
sumx += X[i];
sumy += Y[i];
}
qsort(X, n, sizeof(int), cmp);
qsort(Y, n, sizeof(int), cmp);
sumx -= X[0]*n, sumy -= Y[0]*n;
int Ans1 = 1, Ans2 = 1, minx = sumx, miny = sumy;
for(i = 1; i < n; i++) {
sumx = sumx + (X[i] - X[i-1])*i - (X[i] - X[i-1])*(n-i);
if(sumx == minx)
Ans1 += X[i] - X[i-1];
else if(sumx < minx)
minx = sumx, Ans1 = 1;
}
for(i = 1; i < n; i++) {
sumy = sumy + (Y[i] - Y[i-1])*i - (Y[i] - Y[i-1])*(n-i);
if(sumy == miny)
Ans2 += Y[i] - Y[i-1];
else if(sumy < miny)
miny = sumy, Ans2 = 1;
}
printf("%d %d\n", minx + miny, Ans1*Ans2);
}
return 0;
}/*
2
3
0 0
1 1
2 2
*/
/**********************************************************************************/
/* Problem: a245 "王老師愛兩條線" from 板橋高中練習題 */
/* Language: CPP (1493 Bytes) */
/* Result: AC(1.2s, 1.4MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-15 23:41:02 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t, n, X[1001], Y[1001], i;
ReadInt(&t);
while(t--) {
ReadInt(&n);
int sumx = 0, sumy = 0;
for(i = 0; i < n; i++) {
ReadInt(&X[i]), ReadInt(&Y[i]);
sumx += X[i];
sumy += Y[i];
}
qsort(X, n, sizeof(int), cmp);
qsort(Y, n, sizeof(int), cmp);
sumx -= X[0]*n, sumy -= Y[0]*n;
int Ans1 = 1, Ans2 = 1, minx = sumx, miny = sumy;
for(i = 1; i < n; i++) {
sumx = sumx + (X[i] - X[i-1])*(2*i-n);
if(sumx == minx)
Ans1 += X[i] - X[i-1];
else if(sumx < minx)
minx = sumx, Ans1 = 1;
}
for(i = 1; i < n; i++) {
sumy = sumy + (Y[i] - Y[i-1])*(2*i-n);
if(sumy == miny)
Ans2 += Y[i] - Y[i-1];
else if(sumy < miny)
miny = sumy, Ans2 = 1;
}
printf("%d %d\n", minx + miny, Ans1*Ans2);
}
return 0;
}
上一篇：a254. 畢氏‧三角‧製造
下一篇：a277. 高手寂寞