題目描述

You are playing a coin puzzle. The rule of this puzzle is as follows:

There are N coins on a table. The i-th coin is a circle with ri radius, and its center is initially placed at (sxi,syi). Each coin also has a target position: you should move the i-th coin so that its center is at (txi,tyi). You can move coins one by one and can move each coin at most once. When you move a coin, it must move from its initial position to its target position along the straight line. In addition, coins cannot collide with each other, including in the middle of moves.

The score of the puzzle is the number of the coins you move from their initial position to their target position. Your task is to write a program that determines the maximum score for a given puzzle instance.

輸入

The input consists of a single test case formatted as follows.

N
r1 sx1 sy1 tx1 ty1
:
rN sxN syN tx1 tyN
The first line contains an integer N (1≤N≤16), which is the number of coins used in the puzzle. The i-th line of the following N lines consists of five integers: ri,sxi,syi,txi, and tyi (1≤ri≤1,000,?1,000≤sxi,syi,txi,tyi≤1,000,(sxi,syi)≠(txi,tyi)). They describe the information of the i-th coin: ri is the radius of the i-th coin, (sxi,syi) is the initial position of the i-th coin, and (txi,tyi) is the target position of the i-th coin.

You can assume that the coins do not contact or are not overlapped with each other at the initial positions. You can also assume that the maximum score does not change even if the radius of each coin changes by 10?5.

輸出

Print the maximum score of the given puzzle instance in a line.

樣例輸入

3 2 0 0 1 0 2 0 5 1 5 4 1 -10 -5 10

樣例輸出

2
題意： 給你n(n<=16)個圓的圓心坐標和半徑，以及他們目的地的圓心坐標 問最多有多少個圓可以不和其他圓相交到達目的地 圓只能走直線且只能移動到目的地思路： 直接bfs，2^16的int記錄當前局面，看哪個圓可以移動到目的地而不和其他圓相交就可以擴展到下一個狀態(tài) 主要問題就是判斷一個圓去目的地的路上會不會和其他圓相交 將其他圓的半徑加上當前圓的半徑，問題就轉(zhuǎn)化成了求圓心線（線段）和其他圓會不會相交的問題 如果線段端點有一個在圓內(nèi)則一定相交 如果圓心到線段所在直線的距離大于半徑一定不相交 否則圓心到兩端點的角度都為銳角，則一定相交（早知道就用double了，炸int調(diào)了我兩晚上 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=200; int n,ans; struct Point{ll x,y;Point() {}Point(ll _x,ll _y){x=_x; y=_y;}Point operator -(const Point &b) const{return Point(x-b.x,y-b.y);}ll operator *(const Point &b) const{return x*b.x+y*b.y;} }p1[N],p2[N]; struct orz{int s,d;}; ll r[N]; queue<orz>q; bool vis[1<<20]; ll dis(Point a,Point b) {return (a-b)*(a-b); } bool Inter(int i,int j,int op) {Point O;if (op==1) O=p2[j]; else O=p1[j];Point O1=p1[i],O2=p2[i];int R=r[j]+r[i];if (dis(O1,O)<R*R || dis(O2,O)<R*R) return 0;ll a,b,c,dis1,dis2,ang1,ang2;if (O1.x==O2.x) a=1,b=0,c=-O1.x;else if (O1.y==O2.y) a=0,b=1,c=-O1.y;else a=O1.y-O2.y,b=O2.x-O1.x,c=O1.x*O2.y-O1.y*O2.x;dis1=a*O.x+b*O.y+c;dis1*=dis1;dis2=(a*a+b*b)*(R*R);if (dis1>=dis2) return 1;ang1=(O.x-O1.x)*(O2.x-O1.x)+(O.y-O1.y)*(O2.y-O1.y);ang2=(O.x-O2.x)*(O1.x-O2.x)+(O.y-O2.y)*(O1.y-O2.y);if (ang1>0 && ang2>0)return 0;return 1; } bool check(int x,int s) {bool flag=1;for (int i=0;i<n;i++){if (i==x) continue;if (s&(1<<i)) flag&=Inter(x,i,1);else flag&=Inter(x,i,2);if (!flag) break;}return flag; } void bfs() {ans=0;q.push({0,0});vis[0]=1;while (!q.empty()){orz now=q.front(); q.pop();//for (int i=0;i<n;i++) cout<<((now.s>>i)&1); cout<<endl;ans=max(ans,now.d);for (int i=0;i<n;i++){if ((now.s&(1<<i))==0 && !vis[now.s|(1<<i)] && check(i,now.s) ){q.push({now.s|(1<<i),now.d+1});vis[now.s|(1<<i)]=1;}}} } int main() {scanf("%d",&n);for (int i=0;i<n;i++) scanf("%lld%lld%lld%lld%lld",&r[i],&p1[i].x,&p1[i].y,&p2[i].x,&p2[i].y);bfs();printf("%d\n",ans);return 0; } View Code

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/tetew/p/11391843.html

總結(jié)

以上是生活随笔為你收集整理的Coin Slider的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。