關於IntersectingConvexHull的一個topcoder拼圖

四小時前我第一次問這個問題。事實上，我已經搜索了這個問題超過6個小時，但仍然無法理解。關於IntersectingConvexHull的一個topcoder拼圖

這個問題是關於給你n點給你x [n]和y [n]。你應該找到這些點的兩個子集，它們的凸包相交。您的回答應該是滿足上述規則的案件數量。

給出了平面中點的有限集合S.對於每個有效的i，其中一個點具有座標（x [i]，y [i]）。點都是截然不同，沒有三個是共線的。下面，CH（s）表示集合s的凸包：也就是說，包含集合s的所有凸多邊形中最小的。我們說有序對（S1，S2）是有趣的，如果滿足以下條件被滿足：

1.s1是S

2.s2的一個子集爲S

的一個子集3.集合s1和s2是不相交的（即，它們沒有共同的元素）

4.凸殼CH（s1）和CH（s2）的交點具有正面積注意，從S可能保持未使用（即，它們將不在s1中，也不在s2中），即。你得到所有點的座標：：s x和y。請計算並返回有趣對集的數目，模10^9個+ 7

實例

{1,0，-1，-1,0,1} {1,2,1 ，-1，-2，-1}

返回：14

我們有14個解決方案：

S1 = {0,1,3}，S2 = {2,4,5} s1 = {0,2,3}，s2 = {1,4,5} s1 = {0,1,4}，s2 = {2,3,5} s1 = {0,2,4}，s2 = {1,3,5} s1 = {1,2,4}，s2 = {0,3,5} s1 = {0,3,4}，s2 = {1,2,5} s1 = {1,3,4}，s2 = {0,2,5} s1 = { 0,2,5}，s2 = {1,3,4} s1 = {1,2,5}，s2 = {0,3,4} s1 = {0,3,5}，s2 = {1 ，2,4} s1 = {1,3,5}，s2 = {0,2,4} s1 = {2,3,5}，s2 = {0,1,4} s1 = {1,4 ，5}，s2 = {0,2,3} s1 = {2,4,5}，s2 = {0,1,3}

有很多解決方案我都不懂，以下是其中之一。例如，ccw是什麼？結果由兩部分組成，爲什麼？您能否提供一些算法名稱，一些關鍵字也可以，以便我可以在google上詳細搜索它？

下面是一個示例代碼來解決這個問題：

#include <vector> 
#include <iostream> 

using namespace std; 
const long long mod=1000000007ll; 
struct IntersectingConvexHull{ 
    public: 
     int count(vector<int> x, vector<int> y){ 
      int n = x.size(); 
      long long P2[110]; 
      P2[0]=1ll; 
      for(int i=1;i<=n;i++){ 
       P2[i]=P2[i-1]*2%mod; 
      } 
      long long C[110][110]; 
      for(int i=0;i<=n;i++){ 
       C[i][0]=C[i][i]=1ll; 
       for(int j=1;j<i;j++){ 
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 
       } 
      } 
      long long X[100],Y[100]; 
      for(int i=0;i<=n;i++){ 
       X[i]=x[i]; 
       Y[i]=y[i]; 
      } 
      long long ans=0; 
      for(int i=0;i<n;i++){ 
       for(int j=0;j<n;j++){ 
        if(i==j)continue; 

        int c1=0,c2=0; 
        for(int k=0;k<n;k++){ 
         if(k==i||k==j){ 
          continue; 
         } 
         long long ccw=(X[i]-X[k])*(Y[j]-Y[k])-(Y[i]-Y[k])*(X[j]-X[k]); 
         if(ccw<0){ 
          c1++; 
         } 
         else{ 
          c2++; 
         } 
        } 
        if(c1>=2&&c2>=2){ 
         ans+=((P2[c1]+mod-c1-1)%mod)*((P2[c2]+mod-c2-1)%mod)%mod; 
         ans%=mod; 
        } 
       } 
      } 
      long long A=0ll; 
      for(int i=3;i<=n;i++){ 
       for(int j=3;j<=n-i;j++){ 
        A+=C[n][i]*C[n-i][j]%mod; 
        A%=mod; 
       } 
      } 
      return (A+mod-ans)%mod; 

     } 
};

來源

2016-09-19 Weiheng Li

請不要張貼圖片的代碼。改爲發佈代碼。 –

但由於網站的限制，我無法複製它們。 –

然後通過查看圖像手動鍵入代碼。 –

兩組必須具有至少三個點爲船體的交點到具有非零區域。該代碼計算滿足此條件的分區數量減去零交叉區域的分區數量。（P2是2的冪數，C是二項係數。）

當且僅當存在將兩個外殼分開的線（Hyperplane separation theorem）時，兩個凸包的交點才具有零面積。我認爲我們需要對這個結果進行擴展，實際上，（在正確的假設下）確切地說有兩條線將船體和船體分開。

最後一個循環計算被減數。前一個計算減數的地方就是幾何考慮的地方。代碼在所有的點對上循環，考慮通過它們的直線，通過簽名區域測試來計算每邊的點數。它增加了從每邊選擇兩個或更多點的方法的數量，從而確保如果我們將一對中的第一個點包含在一個船體中並將另一箇中的第二個點包括在另一箇中，則我們得到兩個船體由行支持和分隔。我不知道這段代碼如何處理退化輸入（兩個重複點，三個共線點）。

來源

2016-09-19 16:16:51

關於IntersectingConvexHull的一個topcoder拼圖

回答

相關問題