2015
04-14

# Fruit Ninja

Fruit Ninja is a popular classic game. During the game, fruits will up to the air, and your aim is cut as more fruits as possible with a line.

Even if the line touch a point of a fruit, the fruit also be cut.

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains one integer N (1<=N<=10)
Then N lines follow, each line contains a integer K(3<=K<=10), represent the number points of the fruit, then K*2 integers follow, each two integers represent one point of the fruit.(with anticlockwise order)
I promise all fruits are convex polygon, and any two fruit have no common point.

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains one integer N (1<=N<=10)
Then N lines follow, each line contains a integer K(3<=K<=10), represent the number points of the fruit, then K*2 integers follow, each two integers represent one point of the fruit.(with anticlockwise order)
I promise all fruits are convex polygon, and any two fruit have no common point.

2
3
3 0 0 1 0 1 1
3 1 2 2 1 2 2
3 3 1 3 0 4 0
3
4 0 0 1 0 1 1 0 1
4 2 0 3 0 3 1 2 1
4 0 99 1 99 1 100 0 100

Case 1: 3
Case 2: 2

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")
#define STOP system("pause")

using namespace std;

const int MAX = 35;
struct point {int x,y;};
struct polygon{point p[MAX]; int n;};
polygon g[MAX];
int crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向 顺时针是正
{
return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
bool s2l_inst(point s1,point s2,point l1,point l2)//s是线段，l是直线
{	// xyd包括端点在直线上。xy是穿过
return crossProduct(l1,l2,s1) * crossProduct(l1,l2,s2) <= 0 ;
}
int solve(point a,point b,int n)
{
int ans = 0;
for(int i=0; i<n; i++)
{
int len = g[i].n;
g[i].p[len] = g[i].p[0];
for(int k=0; k<len; k++)
if( s2l_inst(g[i].p[k], g[i].p[k+1], a, b) )
{
ans++;
break;
}
}
return ans;
}

int main()
{
int ncases,n;
int ind = 1;
scanf("%d",&ncases);

while(ncases-- )
{
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d",&g[i].n);
for(int k=0; k<g[i].n; k++)
scanf("%d%d",&g[i].p[k].x, &g[i].p[k].y);
}
if( n == 1 )
{
printf("Case %d: ",ind++);
printf("1\n");
continue;
}
int mmax = 0;
for(int i=0; i<n; i++)
for(int k=0; k<g[i].n; k++)
for(int j=i+1; j<n; j++)
for(int l=0; l<g[j].n; l++)
{
int ans = solve(g[i].p[k], g[j].p[l], n);
if( ans > mmax )
mmax = ans;
}
printf("Case %d: ",ind++);
printf("%d\n",mmax);
}

return 0;
}


1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！