Dream On

今天很残酷,明天更残酷,后天很美好,但绝对大部分是死在明天晚上,所以每个人不要放弃今天。
随笔 - 5, 文章 - 3, 评论 - 2, 引用 - 0
数据加载中……

10年最后一场网络

10年最后一场网络
FZU的11题网络赛1个小时前落下帷幕,辉哥还是那么生猛,一人连A三题……Orz中!!
今天的C题目留下一大遗憾,貌似可以暴力过,自己也写了代码,但是以前没怎么写过计算几何的代码,所以比较吃力!以后多多练习!!
Problem C How many stars

Accept: 33    Submit: 911
Time Limit: 3000 mSec    Memory Limit : 32768 KB

 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
还有可恶的F题目,三人合作写代码也没写完,可能方法不正确,但是开始的时间也有点晚了!老钱甚至为做这个题目做了一个模型,呵呵!
但是按照我们的思路,完全模拟操作的话,除了代码长一点,应该还是可以过得啊!又一大遗憾啊!!
Problem F Megaminx

Accept: 131    Submit: 559
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 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

 Sample Input

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
加油吧,谋事在人,成事在天,如果幸运的话,能进一场FZU的现场赛,如果不行的话,一年之后又是一条好汉!

posted on 2010-10-10 18:04 FireDuck 阅读(320) 评论(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年最后一场网络  回复  更多评论   

@小强
你可以参阅一下博客的解体报告,应该能比我说的清楚http://hi.baidu.com/aekdycoin/blog/item/e87f5f9653423c6255fb969b.html
2010-10-10 22:15 | FireDuck

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理