Accept: 710    Submit: 2038

Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

 Input

 Output

 Sample Input

 Sample Output

Case 1: 1Case 2: 0

我直接用了凸包算法，大材小用了

#include <iostream>

#include <string.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

struct Node

{

    int x;

    int y;

}a[5],b[35];

int s[10];

int top;

int cross(Node a,Node b,Node c)

{

    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

}

int dis(Node a,Node b)

{

    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

int cmp(Node p1,Node p2)

{

    int temp=cross(a[0],p1,p2);

    if(temp>0) return true;

    else if(temp==0&&dis(a[0],p1)<dis(a[0],p2)) return true;

    else return false;

}

int cmp2(Node a,Node b)

{

    if(a.y==b.y)

        return a.x<b.x;

    return a.y<b.y;

}

int graham(int n)

{

    if(n==1){return 0;}

    if(n==2){return 1;}

    if(n>2)

    {

        top=1;s[0]=0;s[1]=1;

        for(int i=2;i<n;i++)

        {

            while(top>0&&cross(a[s[top-1]],a[s[top]],a[i])<=0)

                top--;

            s[++top]=i;

        }

        return top;

    }

}

int n;

int main()

{

    int t;

    scanf("%d",&t);

    int cas=0;

    int ans=0;

    while(t--)

    {

       scanf("%d",&n);

       ans=0;

       for(int i=1;i<=n;i++)

            scanf("%d%d",&b[i].x,&b[i].y);

       for(int i=1;i<=n;i++)

       {

        for(int j=i+1;j<=n;j++)

        {

          for(int k=j+1;k<=n;k++)

          {

            for(int p=k+1;p<=n;p++)

            {

                a[0]=b[i];a[1]=b[j];a[2]=b[k];a[3]=b[p];

                sort(a,a+4,cmp2);

                sort(a+1,a+4,cmp);

                //cout<<i<<" "<<j<<" "<<k<<" "<<p<<endl;

                if(graham(4)==3)

                {

                   // cout<<i<<" "<<j<<" "<<k<<" "<<p<<endl;

                    ans++;

                }

            }

          }

        }

       }

       printf("Case %d: %d\n",++cas,ans);

    }

    return 0;

}