BZOJ 1007(水平可見直線-斜率排序+棧貪心)

1007: [HNOI2008]水平可見直線
Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1830  Solved: 656
[Submit][Status][Discuss]
Description

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

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

Sample Input
3
-1 0
1 0
0 0

Sample Output
1 2

按斜率排序，從小到大插入。
半平面交的特殊情況：
每次
都要保證x坐標<x,top>><top,top'> 否則top不可見（top為棧頂元素）
[cpp]
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<algorithm>  
#include<functional>  
#include<iostream>  
using namespace std; 
#define MAXN (50000+10)  
int n; 
struct line 
{ 
    int k,b,i; 
    friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;   } 
    friend double intx(line a,line b) 
    { 
        return (double)(b.b-a.b)/(a.k-b.k); 
    } 
}a[MAXN]; 
int s[MAXN],size=0; 
void push(int x) 
{ 
    while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--; 
    s[++size]=x;     
} 
bool b[MAXN]; 
int main() 
{ 
    scanf("%d",&n); 
    for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;} 
    sort(a+1,a+1+n); 
    push(1); 
    for (int i=2;i<=n;i++) 
        if (a[i].k>a[i-1].k) push(i); 
//  for (int i=1;)  
    memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1; 
    for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' '; 
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
 int k,b,i;
 friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k; }
 friend double intx(line a,line b)
 {
  return (double)(b.b-a.b)/(a.k-b.k);
 }
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
 while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
 s[++size]=x; 
}
bool b[MAXN];
int main()
{
 scanf("%d",&n);
 for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
 sort(a+1,a+1+n);
 push(1);
 for (int i=2;i<=n;i++)
  if (a[i].k>a[i-1].k) push(i);
// for (int i=1;)
 memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
 for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
 return 0;
}