NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2010國中組初賽
 NPSC2010國中組初賽-about 幽靈特務報到

作者 主題: NPSC2010國中組初賽-about 幽靈特務報到  (閱讀 4143 次)

eop

  • 新手
  • *
  • 文章數: 12
    • 檢視個人資料
NPSC2010國中組初賽-about 幽靈特務報到
« 於: 十一月 27, 2010, 09:30:04 pm »

幽靈題本質題型跟   D. 阿里不達轟!! -- 2009 NPSC 國中組初賽

超級像

基本上...

要垮台


是時間的問題

既然比賽時沒過

就不想寫了
« 上次編輯: 十一月 27, 2010, 10:15:26 pm 由 eop »
記錄

qwqw

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: about 幽靈題
« 回覆 #1 於: 十一月 27, 2010, 10:09:51 pm »

感覺上這個區塊變成你的blog~~標題打正常一點= =(我龜毛?

看到標點就有點不是很想點....
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #2 於: 十一月 28, 2010, 12:33:33 pm »

幽靈題本質題型跟   D. 阿里不達轟!! -- 2009 NPSC 國中組初賽

超級像

基本上...


完全不像= =

阿里不達轟!! 沒有給出爆炸點,
所以,該題是枚舉有哪些炸彈爆炸,並判斷圓有沒有相交。
圓相交可以用圓心連線 <= 兩半徑和來判斷。


此題是給定一個圓,問有多少個矩形與此圓相交。

純粹考計算幾何。

等價於矩形4線段與圓是否有相交。

線段與圓相交可以用線段與圓心距離是否<=半徑來判斷。

由於線段和點的距離,指有可能在兩端點或是點與該線段延伸的直線做垂線的垂直距離,

這題目的線段都是水平或垂直。

垂直距離可以直接從座標差算出,之後兩端點距離也不難求。

只是要注意垂直距離是否有通過線段,這可以從座標上用大於小於判斷。


判定可以在O(1)內做到,於是對每個矩形O(n)掃過一遍即可。


記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #3 於: 十一月 28, 2010, 01:17:37 pm »

我們有學弟O(n)還TLE(江小包)

後來昨天睡前我才想到他用cincout

測資只要1000000比他光在cin就至少15秒=   =

當然TLE
記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #4 於: 十一月 28, 2010, 01:20:30 pm »

晚上他把code 給我時我還看了很久不知道為何TLE=   =
原來在I/O上就有問題了=   =



代碼: [選擇]

#include<iostream>
#include<vector>

using namespace std;

class building
{
   public:
      double cx;
      double cy;
      double lenth;
      double width;

};

int main()
{
   int t;
   cin >> t;
   for(int i(0); i < t; ++i){
      int n;
      cin >> n;
      building *dat = new building[n];
      for(int j(0); j < n; ++j)
         cin >> dat[j].cx >> dat[j].cy
             >> dat[j].lenth >> dat[j].width;

      double bx, by, radius;
      cin >> bx >> by >> radius;
      int sum(0);
      for(int j(0); j < n; ++j){
         if(dat[j].cx > bx){
            dat[j].cx -= dat[j].lenth/2;
            if(dat[j].cx < bx) dat[j].cx = bx;
         }else if(dat[j].cx < bx){
            dat[j].cx += dat[j].lenth/2;
            if(dat[j].cx > bx) dat[j].cx = bx;
         }
         if(dat[j].cy > by){
            dat[j].cy -= dat[j].width/2;
            if(dat[j].cy < by) dat[j].cy = by;

         }else if(dat[j].cy < by){
            dat[j].cy += dat[j].width/2;
            if(dat[j].cy > by) dat[j].cy = by;
         }
         if((dat[j].cx-bx)*(dat[j].cx-bx) + (dat[j].cy-by)*(dat[j].cy-by) <= radius * radius)
            ++sum;

      }

      cout << sum << endl;

   }



   return 0;
}

他好像用vector寫
不過他寄給我前改成陣列(本人不太熟悉vector=   =)
記錄

小包

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #5 於: 十一月 28, 2010, 03:09:51 pm »

晚上他把code 給我時我還看了很久不知道為何TLE=   =
原來在I/O上就有問題了=   =

他好像用vector寫
不過他寄給我前改成陣列(本人不太熟悉vector=   =)

慚愧啊慚愧= =

摁沒錯因為你看不懂我才改成陣列的. .
不過我發現我忘了要delete ==
« 上次編輯: 十一月 28, 2010, 03:21:58 pm 由 小包 »
記錄

annielin

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
    • http://www.wretch.cc/blog/a1131395
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #6 於: 十一月 30, 2010, 08:53:25 pm »

以下是我的同伴寫的
有人可以告訴我他錯甚麼嗎????
代碼: [選擇]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main(){
int t,n,a,b,i,j;
float x[100005][2],y[100005][2],w,l,x1,y1,r;
scanf("%d",&t);
for(i=1;i<=t;i++){
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%f %f %f %f",&x[j][0],&y[j][0],&w,&l);
x[j][1]=x[j][0]+w/2;
y[j][1]=y[j][0]+l/2;
x[j][0]=x[j][0]-w/2;
y[j][0]=y[j][0]-l/2;
}
scanf("%f %f %f",&x1,&y1,&r);
a=0;
b=0;
for(j=1;j<=n;j++){
if((x[j][0]-x1)*(x[j][0]-x1)+(y[j][0]-y1)*(y[j][0]-y1)<=r*r){b=1;}
else if((x[j][0]-x1)*(x[j][0]-x1)+(y[j][1]-y1)*(y[j][1]-y1)<=r*r){b=1;}
else if((x[j][1]-x1)*(x[j][1]-x1)+(y[j][1]-y1)*(y[j][1]-y1)<=r*r){b=1;}
else if((x[j][1]-x1)*(x[j][1]-x1)+(y[j][0]-y1)*(y[j][0]-y1)<=r*r){b=1;}

else if(x[j][0]<=x1 && x1<=x[j][1] && y[j][0]<=y1 && y1<=y[j][1]){b=1;}

else if(x[j][0]<=x1+r && x1+r<=x[j][1] && y[j][0]<=y1 && y1<=y[j][1]){b=1;}
else if(x[j][0]<=x1-r && x1-r<=x[j][1] && y[j][0]<=y1 && y1<=y[j][1]){b=1;}
else if(x[j][0]<=x1 && x1<=x[j][1] && y[j][0]<=y1+r && y1+r<=y[j][1]){b=1;}
else if(x[j][0]<=x1 && x1<=x[j][1] && y[j][0]<=y1-r && y1-r<=y[j][1]){b=1;}

if(b==1){a++;}
b=0;
}
printf("%d\n",a);
}
return 0;
}
記錄

乂淵仔乂

  • 新手
  • *
  • 文章數: 10
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #7 於: 十二月 01, 2010, 07:19:07 pm »

既然超級像
那阿里不達轟你會嗎?

更何況根本不一樣

再說
如果是時間問題的話
都多給你一小時了你還寫不出來
不就是你的問題嗎?

你這種比完賽就不想寫的態度很糟
難道你學程式設計只是為了比NPSC?
上了高中之後NPSC不過是眾多比賽中的一個
等你上了高中就知道了

最後
國中NPSC只要會brute force + 拆包裝就可以拿前六名了
記錄

cbs951214

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #8 於: 一月 02, 2011, 08:34:57 pm »

這題只要幾個if就寫好了
根阿里不達轟差很多

還有樓上的:
他確實會阿里不達轟
而且幽靈特務報到比較簡單
« 上次編輯: 一月 02, 2011, 08:37:14 pm 由 cbs951214 »
記錄

cbs951214

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #9 於: 一月 10, 2011, 09:11:25 pm »

代碼: [選擇]
#include<stdio.h>
#include<math.h>
struct aaa{
    double x,y,l,w;
}a[100001];
int main(){
    int t,n,i,ans;
    double bx,by,br,xx,yy,nx,ny;
     scanf("%d",&t);
     for(;t>0;t--){
        scanf("%d",&n);
        for(i=0;i<n;i++) scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].l,&a[i].w);
        scanf("%lf%lf%lf",&bx,&by,&br);
        ans=0;
        for(i=0;i<n;i++){
            if(a[i].x+a[i].l/2+br>=bx&&a[i].x-a[i].l/2-br<=bx&&a[i].y+a[i].w/2>=by&&a[i].y-a[i].w/2<=by) ans++;
            else if(a[i].x+a[i].l/2>=bx&&a[i].x-a[i].l/2<=bx&&a[i].y+a[i].w/2+br>=by&&a[i].y-a[i].w/2-br<=by) ans++;
            else{
                xx=a[i].x+a[i].l/2;
                yy=a[i].y+a[i].w/2;
                nx=a[i].x-a[i].l/2;
                ny=a[i].y-a[i].w/2;
                if((bx-xx)*(bx-xx)+(by-yy)*(by-yy)<=br*br) ans++;
                else if((bx-xx)*(bx-xx)+(by-ny)*(by-ny)<=br*br) ans++;
                else if((bx-nx)*(bx-nx)+(by-yy)*(by-yy)<=br*br) ans++;
                else if((bx-nx)*(bx-nx)+(by-ny)*(by-ny)<=br*br) ans++;
            }
        }       
        printf("%d\n",ans);
     }   
}
正解~~
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC2010國中組初賽-about 幽靈特務報到
« 回覆 #10 於: 一月 10, 2011, 10:27:55 pm »

题目中说:“兩棟建築物不會互相交叉或覆蓋。”

可事实上,测资里的确有两栋建筑物相互交叉或覆盖的...

//就是因为这个,我WA了老半天的...
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2010國中組初賽
 NPSC2010國中組初賽-about 幽靈特務報到