水果忍者PTA 凸包问题 我的代码还没AC 暂时做个记录

L3-012 水果忍者 （30 分) 2010年风靡全球的“水果忍者”游戏，想必大家肯定都玩过吧？（没玩过也没关系啦~）在游戏当中，画面里会随机地弹射出一系列的水果与炸弹，玩家尽可能砍掉所有的水果而避免砍中炸弹，就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果，则会有额外的奖励，如图1所示。 图 1

现在假如你是“水果忍者”游戏的玩家，你要做的一件事情就是，将画面当中的水果一刀砍下。这个问题看上去有些复杂，让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线，使之可以穿过所有代表水果的线段。 图 2 如图2所示，其中绿色的垂直线段表示的就是一个一个的水果；灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出，对于这样一组线段的排列，我们是可以找到一刀切开所有水果的方案的。

另外，我们约定，如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者，你要如何来找到一条穿过它们的直线呢？

输入格式： 输入在第一行给出一个正整数N（≤10^4 ），表示水果的个数。随后N行， 每行给出三个整数x、y1 、y2 ，其间以空格分隔，表示一条端点为(x,y1 )和(x,y2 )的水果， 其中y1 >y2 。 注意：给出的水果输入集合一定存在一条可以将其全部穿过的直线，不需考虑不存在的情况。坐标为区间 [−10^6 ,10 ^6 ) 内的整数。

输出格式： 在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p1 (x1 ,y1 )和p2 (x2 ,y2 )， 格式为 x1 y1 x2 y2 。 注意：本题答案不唯一，由特殊裁判程序判定，但一定存在四个坐标全是整数的解。

输入样例： 5 -30 -52 -84 38 22 -49 -99 -22 -99 48 59 -18 -36 -50 -72 输出样例： -99 -99 -30 -52

样例的散点图如下：

分析： 这是个凸包问题，先分别求出上凹包线，和下凸包线， 得到如下的折线： 这两条折线中我之前认为一定存在答案。

但是只过了三个测试点，还有三个不知到是什么情况。。。 请各位大佬不吝赐教啊！

代码：

#include
using namespace std;
const int maxn=100001;
class P
{
    public:
        int x,y[2];
};
bool operator < (const P a,const P b)
{
    return a.x<b.x;
}
P p[maxn];

int sta[2][maxn];//Õ» 
int cnt[2];//Õ»¶¥Ö¸Õë 
set s[2];
int n;

long long cross(int a,int b,int c,int line) 
{
    long long x1,x2,y1,y2;
    x1 = (p[b].x-p[a].x);
    x2 = (p[c].x-p[b].x);
    y1 = (p[b].y[line]-p[a].y[line]);
    y2 = (p[c].y[line]-p[b].y[line]);
    return x1*y2-x2*y1;
}
bool check(int p1,int p2,int line)
{
    int x1,x2,y1,y2;
    x1 = p[p1].x;
    x2 = p[p2].x;
    y1 = p[p1].y[line];
    y2 = p[p2].y[line];
//  cout<<"checking "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl; 

    double k = (y2-y1)*1.0/(x2-x1);
    double y;

    for(int i=0;i!=n;i++)
    {
        if(i==p1||i==p2)continue;
        y=k*1.0*(p[i].x-x1)+y1;
        if(((y0.0000001))
        ||((y>p[i].y[0])&&(fabs(y-p[i].y[0])>0.0000001)))
        {
//          cout<<"wrong "<<p[i].x<<" "<<y<<" "<<p[i].y[1]<<" "<<p[i].y[0]<<endl;
            return 0;
        }
    }
    return 1;
}
int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d %d", &p[i].x, &p[i].y[0],&p[i].y[1]);
    }
    sort(p,p+n);
    cnt[0]=cnt[1]=0;
    for(int i=0;i<n;i++)
    {
        while(cnt[0]>2 && cross(sta[0][cnt[0]-2],sta[0][cnt[0]-1],i,0)>=0)
        cnt[0]--;

        while(cnt[1]>2 && cross(sta[1][cnt[1]-2],sta[1][cnt[1]-1],i,1)<=0)
        cnt[1]--;

//      cout<<cnt[0]<<" "<<sta[0][cnt[0]]<<endl;
        s[0].insert(sta[0][cnt[0]]);    

        s[1].insert(sta[1][cnt[1]]);

        sta[0][cnt[0]++]=i;
        sta[1][cnt[1]++]=i;
    }
    s[0].insert(n-1);
    s[1].insert(n-1);

    set::iterator it,is;
    int line=0;
    bool flag=0;
//    for(line = 0;line!=2;line++)
//    {
//      for(it=s[line].begin();it!=s[line].end();it++)
//      {
//          cout<<p[*it].x<<" ";
//      }
//      cout<<endl;
//  }
    for(line = 0;line!=2;line++)
    {
        for(it=s[line].begin();1;it++)
        {
            is = it;
            is++;
            if(is==s[line].end())break;
            if(check(*it,*is,line))
            {
                flag = 1;
                break;
            }
        }
        if(flag)break;
    }
    cout<<p[*it].x<<" "<<p[*it].y[line]<<" "<<p[*is].x<<" "<<p[*is].y[line]<<endl;

    return 0;
}