# Dream On

## 10年最后一场网络

10年最后一场网络
FZU的11题网络赛1个小时前落下帷幕，辉哥还是那么生猛，一人连A三题……Orz中！！

Problem C How many stars

## Problem Description

John has a telescope and he always observes the stars. After each observation, John draws all stars on a paper. To simplify the problem, each star is described as a distinct point in two-dimensional space and no three points are in a line.

There are N stars on the paper. John is so boring that he wants to find some ways to kill the time. He chooses three different points random to form a triangle, and then he wants to know the number of points inside this triangle. There is only one point inside the triangle in Figure 1.

Figrue 1

## Input

The first line of the input contains an integer T (T≤10), indicating the number of cases. Each case begins with a line containing an integer N (3≤N≤1,000), the number of points in the paper. Each of the following N lines contains two integers Xi and Yi 0≤|Xi|, |Yi|≤100,000, 1≤i≤N). The next line contains an integer M (0≤M≤1,000,000), the number of queries John will do. Each of the following M lines contains three integers x, y and z (0≤x, y, z<N), the index of the points John has chosen. The stars are labeled from 0 to N-1.

## Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answers for each query, one on each line.

## Sample Input

2 4 1 1 0 0 0 1 1 0 1 2 1 0 5 0 0 5 0 5 5 0 5 2 1 2 3 1 2 2 0 1

## Sample Output

Case 1: 0 Case 2: 0 1

Problem F Megaminx

## Problem Description

The Megaminx is made in the shape of a dodecahedron, and has 12 face center pieces, 20 corner pieces, and 30 edge pieces. The face centers each have a single color, which identifies the color of that face in the solved state. The edge pieces have two colors, and the corner pieces have three colors. Each face contains a center piece, 5 corner pieces and 5 edge pieces. The corner and edge pieces are shared with adjacent faces. The face centers can only rotate in place, but the other pieces can be permuted by twisting the face layer around the face center. It is showed in Figure 1.

Figure 1

In this problem, the start state of the Megaminx is in Figure 1 where each side of the Megaminx has a single color. According to Figure 2, all sides are numbered as follows: white '0', …, yellow ‘11’. There is a series of operations. What you need to do is to print the end state of the Megaminx after these operations. In each operation, there are two integers s and d. The first integer s indicates which side of the Megaminx should be turned.

Figure 2

The second integer d indicates in which direction the side s should be turned. The value of d is either '1' or '-1' where '1' indicates a clockwise turn and '-1' indicates a counterclockwise turn. The direction is given under the assumption that the viewer is looking directly at the specific side of the Megaminx.

Figure 3 is an example of operation “1 1”. Figure 3(1) indicates the Megaminx before the operation, and Figure 3(2) indicates the Megaminx after the operation.

Figure 3

## Input

In the first line there is an integer T (T≤50), indicating the number of cases. Each case begins with a line containing an integer number N (0≤N≤1,000), the number of the operations. Each of the following N lines contains two integers s (0≤s≤11) and d, s indicates which side of the Megaminx should be turned, d indicates which direction the side s should be turned and d can be either '1' or '-1'.

## Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then output twelve lines indicating the twelve sides according to the side numbers as said above. Each line contains eleven integers separated by a blank space indicating the color of each block. Please output the color of each block according to the block number, the block number is showed in Figure 4.

Figure 4

2 0 1 0 1

## Sample Output

Case 1: 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 Case 2: 0 0 0 0 0 0 0 0 0 0 0 5 5 5 1 1 1 1 1 1 1 1 2 2 1 1 1 2 2 2 2 2 2 3 3 3 3 2 2 2 3 3 3 3 4 4 4 4 4 4 3 3 3 4 4 4 5 5 5 5 5 5 5 4 4 5 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11

posted on 2010-10-10 18:04 FireDuck 阅读(193) 评论(2)  编辑 收藏 引用 所属分类: 感想

## #re: 10年最后一场网络[未登录]  回复更多评论

C题，这个代码能过吗？

#include<iostream>
using namespace std;
struct point
{
int x,y;
}s[1001],os[1001];
int mycompare(const void *ele1,const void *ele2)
{
point *p1,*p2;
p1=(point*)ele1;
p2=(point*)ele2;
if(p1->x==p2->x)
return (p1->y-p2->y);
return (p1->x-p2->x);
}//x up then y up
int xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool pd(point s,point a,point b,point c)
{
if(xmult(a,s,b)*xmult(c,s,b)>=0)
return 0;
if(xmult(a,s,c)*xmult(b,s,c)>=0)
return 0;
if(xmult(b,s,a)*xmult(c,s,a)>=0)
return 0;
return 1;
}
int main()
{
int i,j,m,n,k,sum;
int a,b,c;
while(scanf("%d",&k)!=EOF)
{
for(j=1;j<=k;j++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
os[i].x=s[i].x;os[i].y=s[i].y;
}
qsort(os,n,sizeof(point),mycompare);
//for(i=0;i<n;i++)
//cout<<os[i].x<<" "<<os[i].y<<endl;
scanf("%d",&m);
cout<<"Case "<<j<<":"<<endl;
while(m--)
{
cin>>a>>b>>c;
int maxx=s[a].x>s[b].x?s[a].x:s[b].x;
if(s[c].x>maxx) maxx=s[c].x;
int minx=s[a].x<s[b].x?s[a].x:s[b].x;
if(s[c].x<minx) minx=s[c].x;
int maxy=s[a].y>s[b].y?s[a].y:s[b].y;
if(s[c].y>maxy) maxy=s[c].y;
int miny=s[a].y<s[b].y?s[a].y:s[b].y;
sum=0;
for(i=0;i<n;i++)
{
if(os[i].x<minx) continue;
if(os[i].x>maxx) break;
if(os[i].y<miny||os[i].y>maxy) continue;
if(pd(s[i],s[a],s[b],s[c]))
sum++;
}
cout<<sum<<endl;
}
}
}
}

2010-10-10 20:35 | 小强

## #re: 10年最后一场网络回复更多评论

@小强

2010-10-10 22:15 | FireDuck