NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 NPSC2015國中組初賽-C.跳躍的波利

作者 主題: NPSC2015國中組初賽-C.跳躍的波利  (閱讀 835 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC2015國中組初賽-C.跳躍的波利
« 於: 十二月 09, 2015, 10:04:01 pm »

//  npsc2015-j1c
我使用一個 struct slop {int x, y;}存兩點的斜率,存化成最簡的斜率,若為負統一設定x為負,
若 x位移為0則y設為1或-1 ,若 y位移為0則x設為1或-1,
比較前一個 位移斜率 及接續的 位移斜率是否相等即可
我有三個函數{cmp:比較兩個斜率是否不相等,gcd:最大公因數,getslop(給兩點的x,y位移)算斜率}
代碼: [選擇]
//  npsc2015-j1c
//存化成最簡的斜率,若為負統一設定x為負
//若 x位移為0則y設為1或-1 ,若 y位移為0則x設為1或-1
// 比較前一個 位移斜率 及接續的 位移斜率是否相等即可

#include <iostream>
#include <vector>
using namespace std;
struct slop
{
  int x;
  int y;
};
bool cmp(slop a, slop b)  // != 為 true
{
  return ((a.x != b.x) || (a.y != b.y));
}
int gcd(int a, int b)
{
   int r=a%b;
while(r)
{
  a=b; b=r; r=a%b;
}
return b;
}
slop getslop(int xd, int yd)
{
   slop m; //斜率
if(xd==0)
{
m.x=0;
m.y= (yd<0?-1:1);
return m;
}
if(yd==0)
{
m.y=0;
m.x= (xd<0?-1:1);
return m;
}
bool sgn = (xd*yd<0);   // 斜率為 負
xd=abs(xd); yd=abs(yd);
int g = gcd(xd, yd);
xd /= g; if(sgn) xd*=-1;
yd /= g;
m.x = xd;  m.y=yd;
return m;
}
int main( )
{
   int  n , i , j , k;
   int x[2],y[2], xd,yd;
   slop m[2];
   while(cin >> n)
   {
vector <int> ans;
int cnt=0;
cin >> x[0] >> y[0] >> x[1] >> y[1];
m[0] = getslop( x[1]-x[0] , y[1]-y[0] );  //第0-1點 斜率
//cout << "0-1:" << m[0].y << "/" << m[0].x << endl;
for(i=2,j=0; i<n; ++i,j=1-j)
{
cin >> x[j] >> y[j];
m[1-j] = getslop( x[j]-x[1-j] , y[j]-y[1-j] );
if( cmp(m[0] , m[1]) )
{
  ++cnt;
  ans.push_back(i);
}
//cout << i-1 << "-" << i << ":"  << m[1-j].y << "/" << m[1-j].x << endl;
}
//cout << endl;
cout << cnt << endl;
for(i=0; i<ans.size(); ++i)
  cout << ans[i] << endl;
}
   
   return 0;
}
/*
7
0 0
1 1
2 2
1 2
0 2
1 1
2 0
5
0 0
0 1
1 1
1 0
0 0
------------
2
3
5
3
2
3
4
*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 NPSC2015國中組初賽-C.跳躍的波利