bzoj 1007 [HNOI2008] 水平可見直線 題解

【原題】

Description

Input

第一行為N(0 < N < 50000),接下來的N行輸入Ai,Bi

Output

從小到大輸出可見直線的編號，兩兩中間用空格隔開,最後一個數字後面也必須有個空格

Sample Input

Sample Output

【分析】這道題A起來可真的不容易。開始周圍大神都說是單調棧，於是匆忙看題解——因為心沒靜下來，而且其他大神的題解過於簡略（一般都是貼代碼），我愣是沒看懂。於是只好按照棧的思想，自己去推了。

如圖，這是我畫的一幅圖畫。為了計算的有序性，我們先按K的坐標降序排序（即是K是負數）。然後我O(N)去掃每根直線。如圖，設綠線和藍線已經在棧中了。如果我們盡量想讓藍線被覆蓋，該怎麼辦?（顯然綠線不能被覆蓋）。設紅線與綠線的交點是（X1，Y1）紅線與藍線的交點是（X2，Y2）。經過畫圖發現，如果X1<=X2，那麼藍線一定是看不到的。感性的想，假設紅線相對於綠線和藍線在下面，那麼藍線必定有一部分能看到。而此時X1就大於X2了。

【代碼】

#include
#include
#define N 50005
using namespace std;
struct arr{int k,b,id;}a[N],aa[N];
double x_in(arr c,arr d){return (d.b-c.b+0.0)/(c.k-d.k+0.0);}
int n,i,s[N],top,M;double x1,x2;
bool cmp1(arr a,arr b){return a.k>b.k;}
bool cmp2(int c,int d){return a[c].ida[M].b) a[M].b=aa[i].b,a[M].id=aa[i].id;
  s[1]=1;top=1;
  for (i=2;i<=M;i++)
  {
    while (top>=2)
    {
      x1=x_in(a[s[top-1]],a[i]);
      x2=x_in(a[s[top]],a[i]);
      if (x1<=x2+1e-6) top--;else break;
    }
    s[++top]=i;
}
  sort(s+1,s+top+1,cmp2);
  for (i=1;i<=top;i++) printf(%d ,a[s[i]].id);
  return 0;
}