议事大厅-【赛码网】..

题目描述：

给出平面上的n个点，任意三个点可以构成一个三角形。找出这些面积最小的三角形和面积最大的三角形，输出其面积

输入

输入包含多个测试样例。每个测试样例第一行包含一个整数n（3<=n<=2,000），表示点的个数。接下来有n行，每行有2个整数x和y（-10,000<=x,y<=10,000），表示一个点的坐标。没有测试样例会包含两个一样的点。输入以一行包含一个0结束。

输出

对于每个测试样例，输出一行：先是其可能构成的三角形中最小的面积，然后是最大的面积。请输出保留一位小数，最小面积和最大面积之间有一个空格。请不要输出多余的空格，两组答案之间不要有空行。

样例输入

-5 -5

-4 3

4 1

3 -2

样例输出

10.5 33.0

#include<iostream>

#include<vector>

#include<string>

#include<sstream>

#include<cstring>

#include<math.h>

using namespace std;

float max = 0, min = 0,a,b,c,l,temparea=0;

int ff = 0;

float trarea(vector<int>& p0, vector<int>& p1, vector<int>& p2){

a = sqrt((p0[0] - p1[0])*(p0[0] - p1[0]) + (p0[1] - p1[1])*(p0[1] - p1[1]));

b = sqrt((p0[0] - p2[0])*(p0[0] - p2[0]) + (p0[1] - p2[1])*(p0[1] - p2[1]));

c = sqrt((p2[0] - p1[0])*(p2[0] - p1[0]) + (p2[1] - p1[1])*(p2[1] - p1[1]));

l = (a + b + c) / 2;

return sqrt(l*(l-a)*(l-b)*(l-c));

}

void DFS(int depth, vector<int>& D, vector<int>& V, int n, vector<vector<int> >& points){

if (depth == n){

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

cout << D[i] << ' ';

cout << endl;

temparea=trarea(points[D[0]], points[D[1]], points[D[2]]);

if (max < temparea)

max = temparea;

if (ff == 0){

min = temparea;

ff = 1;

}

if (min>temparea)

min = temparea;

return;

}

for (int i = 0; i < n; i++){

if (V[i] == 0){

D[depth] = i;

V[i] = 1;

DFS(depth + 1, D, V, n,points);

V[i] = 0;

}

int main(){

//int data[N];

// memset(data, 0, sizeof(int)*N);

int n;

vector<int>p(2,0);

if (cin>>n){

vector<vector<int> >points(n,p);

vector<int> D(n, 0),V(n,0);

for (int i = 0; i < n;i++){

cin >> p[0];

cin >> p[1];

points[i] = p;

}

for (int i = 0; i < n; i++){

cout << "x:" << points[i][0] << " y:" << points[i][1] << endl;

}

DFS(0,D,V,n,points);

printf("%.1f %.1f\n", min, max);

min = 0, max = 0, ff = 0;

}

system("pause");

return 0;

}

coder_2UJEZR9D

AC时间超时。。。本地通过

2017-04-16 21:15

coder_2UJEZR9D

第二题比较简单，可惜没来得及做。。

题目描述：

对于一个字符串，定义其复杂度为不同字符的个数。例如，字符串“string”的复杂度为6，字符串“letter”的复杂度为4。

假设你喜欢复杂度为1或者2的字符串。你的朋友给你一个字符串，你通过擦除一些字符，将其变为你喜欢的字符串。请计算最少需要擦除的字符个数，使得最后的字符串的复杂度最多为2。

输入

每次输入含有一条测试。你的程序可能要在不同的输入上运行多遍。输入包含一行字符串，最少有1个，最多有100个小写字符。

输出

一个整数，表示将输入字符串化简到复杂度为1或者2所需要擦除的最少字符个数。

样例输入

string

letter

aaaaaa

uncopyrightable

ambidextrously

assesses

assassins

样例输出

#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<cstring>
#include<math.h>
using namespace std;
int main(){
	string ss;
	int data[26];
	while (cin >> ss){
		memset(data,0,sizeof(int)*26);
		int count = 0;
		for (int i = 0; i < ss.length(); i++)
			data[ss[i] - 'a']++;
		for (int i = 0; i < 26;i++)
		if (data[i]>0)
			count++;
		if (count <= 2)
			cout << 0 << endl;
		else{
			cout << count - 2 << endl;
		}
	}
	system("pause");
	return 0;
}

2017-04-16 21:17

coder_QZ89WS6A

#include<iostream>

#include<string>

#include <vector>

#include <iomanip>

#include <cmath>

using namespace std;

double lineth(int x1,int y1,int x2,int y2)

{

double len;

len=sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2));

return len;

}

int main()

{

int num;

cin>>num;

while (num>0)

{

vector<int> X,Y;

X.resize(num);

Y.resize(num);

for (int i=0;i<num;i++)

{

cin>>X[i]>>Y[i];

}

double minarea=999999,maxarea=0;

double a,b,c,p;

for (int m=0;m<=num-3;m++)

{

for (int n=m+1;n<=num-2;n++)

{

for (int k=n+1;k<=num-1;k++)

{

a=lineth(X[m],Y[m],X[n],Y[n]);

b=lineth(X[m],Y[m],X[k],Y[k]);

c=lineth(X[k],Y[k],X[n],Y[n]);

if ((a+b)<=c||(b+c)<=a||(a+c)<=b)

{

continue;

}

p=(a+b+c)/2;

double nowarea=sqrt(p*(p-a)*(p-b)*(p-c));

//cout<<"now"<<nowarea<<endl;

if (nowarea<minarea)

{

minarea=nowarea;

}

else if (nowarea>maxarea)

{

maxarea=nowarea;

}

if (maxarea==0)

{

maxarea=minarea;

}

cout.fixed;

cout.precision(1);

cout<<minarea<<" ";

cout<<maxarea<<endl;

cin>>num;

}

return 0;

}

我这样写提示输出超限，请问问题出在哪里？谢谢

2017-04-16 21:33

test

写了这个system("pause");能对？应该会超时的。去掉。

2017-04-17 06:18